AWSサポートに質問をしました。

画像にありますように、既存の ELB に SSL 証明書を追加しようとすると Server Certificate not found for the key というエラーが発生します。
こちらの解消方法をご教授いただけないでしょうか？
よろしくお願いいたします。

回答はこちら

お問い合わせ頂き誠にありがとうございます。

画像にありますように、既存の ELB に SSL 証明書を追加しようとすると Server Certificate not found for the key というエラーが発生します。

マネジメントコンソール（以下MC）から ELB に SSL 証明書をアップロード・変更する場合、保存時にご連絡いただきましたエラーが発生することがございます。

証明書自体に問題がない場合、本件は MC の既知の不具合によって発生してしまったと考えられます。
こちらの不具合につきまして修正予定となっているものの、修正が完了する日時につきましては未定となっております。
ご迷惑をおかけいたしまして恐れ入りますが、修正されるまでの間に再度発生してしまった場合には、今回の方法や後述いたします AWS CLI でのご対応をお願いいたします。

上記のエラーが発生した場合、実際には証明書のアップロードまでは成功している場合があります。
その場合にはMCで証明書の変更を再度お試しいただきますと、対象の証明書が選択可能になり、その場合には更新も成功します。

なお上記エラーメッセージが発生した場合の別のワークアラウンドとしては、AWS CLI にて回避していただく方法をお勧めしております。

AWS CLI を使用した SSL 証明書の置き換え
http://docs.aws.amazon.com/ja_jp/elasticloadbalancing/latest/classic/elb-update-ssl-cert.html#us-update-lb-SSLcert-cli

その後

何回かトライしてから見にいってみると証明書は登録されていた状態になっていたので、アップロードは成功していました。
かろうじて、画面上からできたのでよかったですが、同じところにハマる人がいた時のためにメモです。