To fix this problem, simply delete the debug.keystore file.
The default storage location for AVDs is
- In
~/.android/
on OS X and Linux. - In
C:\Documents and Settings\<user>\.android\
on Windows XP - In
C:\Users\<user>\.android\
on Windows Vista and Windows 7.
Also see this link, which can be helpful.