Eso me ha pasado a mí alguna vez y la verdad es que no entiendo por qué, debe ser que algún archivo odex de la aplicación que vas a sustituir se queda por ahí tocando las narices.
Para solucionarlo a mi me ha bastado con desinstalar desde el mismo Google Play la aplicación que quieres actualizar. Cuando termine le das al botón de instalar y te quedas con la última versión.