Acontece que eu estava perdendo que minha chave não era uma chave RSA, eu precisava fazer o seguinte:
openssl rsa -in company.key -out company_rsa.key
Temos um ELB existente no EC2. Ele possui um certificado ssl curinga emitido pelo GoDaddy. Eu baixei o novo .crt e gd_bundle.crt do GoDaddy.
Em ec2, vou ao balanceador de carga, clico no certificado e escolho fazer o upload de um novo certificado. Eu copio a chave privada existente no campo de chave privada. O conteúdo do novo .crt no campo de certificado público e o conteúdo de gd_bundle.crt no campo da cadeia de certificados.
Quando tento salvá-lo, recebo o erro "Certificado de chave pública inválido".
Os certificados estão no formato PEM (ou parecem ser)