Jeivo, prueba una cosa:
Cuando entres en el Market y te indique que tienes una actualización, no te la descargues.
Espérate unas 24 horas a ver si te sale el icono en la barra de notificaciones.
Parece un tontería, pero pruébalo, no pierdes nada.
Un saludo.