I'm surprised no one has mentioned this, but you can go to Google Play developer support, and they will work with you to create a new upload key:
https://support.google.com/googleplay/android-developer/contact/otherbugs
I filled an issue, and they contacted me within 1 day.
Update: After following their email instructions I was able to create a new upload key, and it was enabled a few days later! Problem solved.