Desinstala todo lo que tenga que ver con Google, incluido los servicios de Google, seguramente necesites ser Root y hacerlo con alguna aplicación tipo Titanium.
Y a probar.
Yo te digo que a mi a veces me ha ido, otras veces no, no hay un metodo, es una locura pero es así.