Si utilizáis lucky patcher o similar se crean archivos .odex, entonces a la hora de actualizar da ese error.
Solución: con rootexplorer te vas a /data/app/ y borras el .odex de la aplicación que quieras actualizar.
A ver si así tenéis más suerte.
Salu2,
SiWy
