Si mie mi se intampla asta, dar am rezolvat uite cum am facut:
Mergeti la Setari - Aplicatii - Toate, mergi jos si cautati Google Play Store (sau Market) si selectati.
Apasati pe Oprire fortata, Ok, apasti Sterge Data si in cazul in care optiunea Golire cache este activata apasati pe ea si Ok.
Mergi inapoi in lista cu aplicatii, cautati Google Service Framework si apasati pe el.
Aceeasi procedura ca ma sus, Oprire fortata, Sterge data, Golire cache si Ok.
Restartati telefonul si gata, in cazul in care apare din nou aceeasi problema, faceti aceeasi procedura inca odata si la fel restartati telefonul.