Well I have to say I've lost a lot of respect for Google today.
I got a message on my phone from the Google account to say something suspicious had possibly gone on and I should change my password.
So I logged into the web site and double checked and changed my password. Changed on the web browser OK and other machines but not on the phone. No way.
You enter your details (username, password and 2 factor from Authenticator) and you get "sorry, there seems to be a problem. please try again." Tried this a few times, rebooted etc but no joy.
So I deleted the account from the phone and tried re-adding it. Nope still the same problems. Search for this error and quite a few people have had it. The suggested try an App specific password. Nope it say dah, enter your account password not an app specific one.
Finally got frustrated and removed the 2 factor from the account and that did it. So you have to unsecure your account to get your phone on. How bad is that?
Hope this saves someone else some frustration.
Now to try turning two factor back on and see if it breaks.