¿has toquiteado con root el sistema?
a mi me ha pasado más o menos lo mismo, y sabía que podía ser porque en su momento me cargué el amazon mp3. Luego lo he intentado actualizar a mano y entonces sí que me ha indicado claramente que ese era el problema, así que he tenido que andar instalando de nuevo ese apk, en fin, un buen rato buscando la información y consiguiendo que funcione.
Pero lo primero que tienes que hacer es verificar si la actualización a mano te funciona o te da algún aviso.