On Vista, this worked:
DOS: del c:\user\dad\.android\debug.keystore
ECLIPSE: In Project, Clean the project. Close Eclipse. Re-open Eclipse.
ECLIPSE: Start the Emulator. Remove the Application from the emulator.
You are good to go.
I was pretty worried when I say that error, but I fixed it from reading here and playing around for 10 minutes.