Con Root Explorer ve a /data/app y busca el .odex de la aplicación que quieres instalar y bórralo.
A veces cuando pruebas diferentes .apks de una misma aplicación, al desinstalar no se borra el .odex y surge este problema.
También puedes instalar Lucky Patcher, que al arrancar busca los .odex de aplicaciones que ya no están y los elimina. En ambos casos necesitas root.