I managed to fix the issue, by doing this:
1) (this step might not have helped, try steps 2+3 first, then this one and the second and third again if they alone didn't suffice) deleted all app-data of Google account manager and Google backup transport in settings-> apps
2) I rebooted
3) I...