Si no dás con el problema, yo lo haria. Puede ser algun tipo de malware, o algun bug que imposibilite sincronizar con google. Si tienes rooteado yo haria un backup i flasheo limpio y tira 'pa alante.
Parece un problema de software y no de hardware, ya que deduzco que la navegación y las demás cosas te funcionan bien.
Volver a una rom nueva es la solución segura, pero muy posiblemente si insistes investigando acabes de dar con la fuente del problema. Yo nunca había oído este fallo, por lo que poco puedo ayudar, pero la lógica que dice que esto se cura con un factory reset.
