Eu havia carregado meu aplicativo no Google Play (quando era chamado de Android Market) há algum tempo.

Hoje atualizei o aplicativo, mas excluí o keystore anterior e criei um novo.
Ao fazer o upload, indica que o APK deve ser assinado com os mesmos certificados da versão anterior:

Falha no upload

Você enviou um APK assinado com um certificado diferente para os APKs anteriores. Você deve usar o mesmo certificado.

Seus APKs existentes são assinados com os certificados com impressões digitais:
[SHA1: 89: 2F: 11: FE: CE: D6: CC: DF: 65: E7: 76: 3E: DD: A7: 96: 4F: 84: DD: BA: 33]
e os certificados usados para assinar o APK que você enviou têm impressões digitais:
[SHA1: 20: 26: F4: C1: DF: 0F: 2B: D9: 46: 03: FF: AB: 07: B1: 28: 7B: 9C: 75: 44: CC]

Mas não tenho esse certificado e não quero excluir e republicar o aplicativo, porque ele possui usuários ativos.

O que posso fazer para assinar meu aplicativo com novo certificado?