I ran into this and found a workaround. If you look in a copy of your appDef (in a text editor) from when you had it working before you replaced it with the new keystore, in the signing section you will see an obfuscated password and alias. Grab those and put them in your appdef and point it to the old keystore and it will work.
Another option I have read about but not done is to get Google to reset the keystore. Go to this link: