Erro SSL_ERROR_NO_CYPHER_OVERLAP com certificado assinado

Minha empresa forneceu um aplicativo baseado em Tomcat/MySQL para um cliente que, por padrão, usa http. A pedido do cliente, habilitei isso para usar https criando um certificado autoassinado. Isso funcionou sujeito ao erro esperado do navegador ao usar um certificado autoassinado.

Depois de um teste de penetração, eles decidiram que precisávamos desabilitar alguns protocolos e cifras SSL obsoletos, então alterei o conector SSL em meu tomcat server.xml para ficar assim:

    <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" />

Isso satisfez o teste de penetração e o aplicativo continuou a funcionar nos três navegadores principais (Chrome, Firefox e IE). No entanto, o teste de penetração também sinalizou que, idealmente, não deveríamos usar um certificado autoassinado, então, seguindo estes guias , criei um CSR e fiz com que o cliente criasse um certificado assinado em seu domínio interno (o servidor pode ser acessado por um par de URLs diferentes, daí a necessidade de criar um CSR com um SAN).

Adicionei o certificado a um novo keystore e corrigi o caminho no arquivo server.xml de forma apropriada. Agora, quando tento conectar, recebo o seguinte erro (isso é do Firefox, mas todos os navegadores produzem um erro semelhante):

Falha na Conexão Segura

Ocorreu um erro durante uma conexão com 172.31.1.36:8443. Não é possível se comunicar com segurança com o par: sem algoritmo(s) de criptografia comum. Código do erro: SSL_ERROR_NO_CYPHER_OVERLAP

A página que você está tentando visualizar não pode ser exibida porque não foi possível verificar a autenticidade dos dados recebidos. Entre em contato com os proprietários do site para informá-los sobre esse problema.

Meu entendimento é que o certificado não controla quais cifras ou protocolos devem ser usados, então não entendo por que isso aconteceu. Isso é um erro que cometi ao produzir o CSR ou pode ser um erro que o cliente cometeu ao gerar o certificado?

-EDITAR-

Parece que estou recebendo erros em todos os lugares que viro. Se eu tentar importar a chave para um keystore, recebo isto:

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

Ou isto:

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

Eu tenho o cliente para me enviar a cadeia de certificados e quando tento importar recebo este erro:

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

Eu encontrei algumas soluções sobre como converter o arquivo pkcs para x.509, mas depois recebi outros erros, então estou totalmente preso agora.