A mi me ha pasado varias veces. Te dejo las 2 soluciones que a mi me dan resultado.
Lo más normal, ir a ajustes, aplicaciones, todas, servicios de google play, borrar datos, reiniciar, entrar en google play y listo.
La segunda (esta suele ocurrir si has usado freedom o hacheado el play) con un explorador
root, ir a etc y hay un borrar un archivo host.
Espero te sirva de ayuda