Для меня ответом было просто удалить файл debug.keystore.Место хранения по умолчанию для AVD находится в ~ / .android / в OS X и Linux, в C: \ Documents and Settings \ .android \ в Windows XP и в C: \ Users \ .android \ в Windows Vista.
В Eclipse я «очистил» проект, удалил приложение и TestApp из эмулятора и - вуаля, все снова заработало нормально.