То, что сказал Джичао, всегда работает для меня.
Обычно, когда я вижу эту ошибку, если я использую Eclipse, я закрываю и снова открываю программу.Затем я удалю приложение с целевого телефона.Это иногда решает проблему, но не всегда.
Далее я открою командный терминал и зайду в android-sdk, затем запусту:
./adb install <AppName>.apk
Это делает то же самое, что и черезEclipse работает, но выдает сообщение об ошибке.
(9 раз из 10 он просто говорит «INSTALL_ALREADY_EXISTS», и я иду и снова удаляю приложение с целевого телефона, затем запускаю adb, и у меня все отлично.)