U mnie pomogła taka akcja:
Wejść w Ustawienia, następnie Aplikacje, zakładka Wszystkie
Wybrać Sklep Play
Wybrać "Wyczyść dane", "Wyczyść pamięć podręczną" następnie "Wymuś zatrzymanie"
Cofnąć się do Aplikacje
Wybrać, Google Services Framework
Wybrać "Wyczyść dane", następnie "Wymuś zatrzymanie"
Cofnąć się do Aplikacje
Wybrać Usługi Google Play
Wybrać "Wyczyść dane", następnie "Wymuś zatrzymanie"
Zrobić restart