Mein Freund hatte mit seinem Streak seit ein paar Tagen das selbe Problem.
Wir waren auch schon ratlos, haben das überfällige Update auf 2.2.2 gemacht, was aber nichts half.
Dann habe ich nach Lösungen gegooglet, wobei ich auf diesen Thread gestoßen bin, was einiges an Arbeit und rumprobieren erspart hat.

Folgendes hat geholfen:
Unter Einstellungen -> Datenschutz habe ich die Häkchen bei "Meine Daten sichern" und "Automatisches Wiederherstellen" rausgemacht, das Telefon danach aus und wieder eingeschaltet und danach funktionierte alles wieder!

Unter "Meine Daten sichern" kam auch so eine Meldung, dass auf allen google-Servern alle Daten gelöscht werden, vermutlich lag das Problem an einem dieser google-Server...