OK yttrium, Actually I was able to do that as you suggested, thanks again! I had to go into Application Manager, stop the app, clear the data and uninstall it. Then recompiling using the debug key worked.
Whew! So at least I can show my boss!
Question, why would making a new key break the database? Is that the "installation failure" that the IDE talks about? If so, how do I manually uninstall the program so that I can install a signed one?
So far, repeating the procedure above that allowed me to install a working, debug-signed app, does not work when pointing to the signed key file. Is there anything funky about the key file names or passwords? I have a mixture of upper and lower case letters in both as well as a number in the password.