Tomcat – SSL_ERROR_NO_CYPHER_OVERLAP error with signed certifcate

My company has supplied a Tomcat/MySQL based application to a customer that by default uses http. At the request of the customer I enabled this to use https by creating a self-signed certificate. This worked subject to the expected browser error when using a self-signed cert.

After a pen-test they decided we need to disable some deprecated ssl protocols and and ciphers, so I amended the ssl connector in my tomcat server.xml to look like this:

    <Connector port="8443" protocol="HTTP/1.1" SSLEnabled="true"
    maxThreads="150" scheme="https" secure="true"
    clientAuth="false" sslProtocol="TLS" sslEnabledProtocols="TLSv1.2,TLSv1.1" ciphers="TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256,TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA,TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384,TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA,TLS_ECDHE_RSA_WITH_RC4_128_SHA,TLS_RSA_WITH_AES_128_CBC_SHA256,TLS_RSA_WITH_AES_128_CBC_SHA,TLS_RSA_WITH_AES_256_CBC_SHA256,TLS_RSA_WITH_AES_256_CBC_SHA,TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256,TLS_DHE_RSA_WITH_AES_128_GCM_SHA256,TLS_WITH_AES_128_GCM_SHA256"
    keystoreFile="/path/to/keystore/file"
    keystorePass="password" />

This satisfied the pen test and the application continued to work in all three main browsers (Chrome, Firefox and IE). However, the pen test also flagged that we should ideally not be using a self-signed cert so, by following these guides, I created a CSR and got the customer to create a certificate signed to their internal domain (the server could be accessed by a couple of different URLs hence the need to create a CSR with a SAN).

I added the certificate to a new keystore and amended the path in the server.xml file appropriately. Now, when I try to connect I get the following error (this is from Firefox, but all browsers produce a similar error):

Secure Connection Failed

An error occurred during a connection to 172.31.1.36:8443. Cannot
communicate securely with peer: no common encryption algorithm(s).
Error code: SSL_ERROR_NO_CYPHER_OVERLAP

The page you are trying to view cannot be shown because the authenticity of the received data could not be verified.
Please contact the web site owners to inform them of this problem.

My understanding is that the cert does not control what ciphers or protocols should be used so I don't understand why this has happened. Is this an error I've made in producing the CSR or could it be an error the client has made with generating the cert?

-EDIT-

I seem to be getting errors everywhere I turn. If I try to import the key to a keystore I get either this:

cat <keyfile> | openssl  pkcs12 -export -out <keystore>.p12
Enter pass phrase:
unable to load certificates

Or this:

keytool -importkeystore -srckeystore <keyfile> -srcstoretype pkcs12 -destkeystore <keystore>.jks
Enter destination keystore password:
Re-enter new password:
Enter source keystore password:
keytool error: java.io.IOException: toDerInputStream rejects tag type 45

I've got the customer to send me the certificate chain and when I try to import that I get this error:

keytool -import -trustcacerts -alias tomcat -file <certchain>.p7b -keystore <keystorefile>.jks
Enter keystore password:
keytool error: java.lang.Exception: Input not an X.509 certificate

I found some solutions on how to convert the pkcs file to x.509 but then I got other errors, so I'm totally stuck now.