"ERROR: Cannot recover key" When Exporting Signed Android App with Existing Keystore

I have an existing keystore with a password and a few keys with different passwords inside for the different apps I have exported and uploaded to Google Play. Now I have recently imported one of the app's projects, did some significant modifications to it and I am trying to export it using the same keystore and choosing the same alias/password as I did while initially creating it. The problem is that after the step where I choose the key alias and enter key password I see "ERROR: Cannot recover key". I suspect that I might be entering a wrong key password (note that the keystore password is the correct one, so this is not the reason for the issue). I tried creating a new alias and exporting the app under it, but Google Play won't accept this file unless it's signed with the same certificate. I really don't know how to proceed in this scenario besides trying to brute force the key password. If you think this is the only path, do you know a good brute force cracking tool for keys in a keystore, for which I already know the password to? The keystore is a .reg file, created with Eclipse's Export wizard.