Как вы загрузили apk на ваше устройство? Используя консоль с adb, убедитесь, что у вас установлена опция переустановки. В противном случае проверьте, не сообщило ли вам Eclipse, оно переустановило приложение (проверьте консоль в Eclipse). Последнее, что нужно попробовать: удалить старую версию с вашего устройства и установить ее снова.