Google account not working on Windows Phone 8

Recently, I did a reset on my Windows 8(.1) phone, and after everything was successfully restored from the backup, BUT the Google accounts. The Google account said in a notification that it needs my attention, but afterwards clicking on the resync button just got me back to this message after some time, so it was an infinite loop. I was searching around the interwebs, but found no answers to this problem; but then I remembered, that I've secured my Google account with 2 step verification, and it listed my phone as a valid device. But after the reset, something must have changed, and it was no longer the same device for Google. The solution was, to open Internet Explorer on the phone, and go to https://accounts.google.com/b/0/DisplayUnlockCaptcha to reset this binding by logging in to your account, and re-enable the device. Afterwards returning to Settings / account I could modify / add new Google accounts.