Si el mensaje te aparece al instalar una aplicación que ya has tenido instalada y que has desinstalado, es porque te ha dejado el archivo ODEX de la aplicación en la carpeta de instalación:
/data/appnombre de la aplicación.odex.
Tienes que eliminarlo, pero sólo podrás entrar en esas carpetas de sistema si eres root y con una explorador de archivos tipo Root Explorer.
Saludos