Решилось так:Debug Certificate expired on 10.03.12 10:39 <имя проекта> Unknown Android Packaging Problem
1) В меню Eclipse выполняем Project > Clean
2) Удаляем файл debug.keystore в папке .android
Правда после этого перестали из Eclipse запускаться все остальные проекты-приложения, которые уже были проинсталлены в AVD. Проблема решается их удалением и установкой заново.