Contact Google. You can now reset your key without having to re-sign your apk.
https://support.google.com/googleplay/android-developer/answer/7384423#reset
Thanks for contacting Google Play Developer Support.
I understand you're not able to use your app’s original keystore.
Unless you are enrolled in Google Play app signing, the only solution to this issue is to publish a new app with a new package name and a new key. In order to transition existing users to the new app, you’ll need to update the original app’s description with a link to the new app and unpublish the original app.
I absolutely understand this is a significant inconvenience, however, due to security concerns Google does not keep a copy of your keystore and at this time we do not support the deletion of apps or the re-use of package names.
This is what i recived from Google Support, so i guess my app updates are over... :(
This is pretty sad...