I had uploaded my app to Google Play (back when it was called Android Market) some time ago.
Today I updated the app, but I had deleted the previous keystore and created a new one.
When uploading, it says the APK must be signed with the same certificates as the previous version:
You uploaded an APK that is signed with a different certificate to your previous APKs. You must use the same certificate.
Your existing APKs are signed with the certificate(s) with fingerprint(s):
[ SHA1: 89:2F:11:FE:CE:D6:CC:DF:65:E7:76:3E:DD:A7:96:4F:84:DD:BA:33 ]
and the certificate(s) used to sign the APK you uploaded have fingerprint(s):
[ SHA1: 20:26:F4:C1:DF:0F:2B:D9:46:03:FF:AB:07:B1:28:7B:9C:75:44:CC ]
Nothing. Read the documentation: Publishing Updates on Android Market
Before uploading the updated application, be sure that you have incremented the android:versionCode and android:versionName attributes in the element of the manifest file. Also, the package name must be the same and the .apk must be signed with the same private key. If the package name and signing certificate do not match those of the existing version, Market will consider it a new application and will not offer it to users as an update.