Help New phone and Authenticator is not playing ball

[dingdongdingers]

Got a new Nexus 5 ( not 5x) and trying to setup the authenticator again.
Open the app, begin setup, I select my gmail account from the available google accounts, and it says to continue on a computer.... to enable 2 step verification for your Google account, please visit accounts.google.com/security on a computer.
I do so, and there is nothing about changing phones anywhere in the 2 step verification page.

Locked out of my server so really need this to work!

can anyone point me in the right direction?

 

[yabadabadoo]

Turn off 2 step verification on your Google account. Re-enable it using your new phone.

 

[dingdongdingers]

cheers yabadabadoo, but not working, stuck in a looping hell.
have turned 2 step off on my account, tried the authenticator, nothing.
have turned 2 step on on my account, then tried authenticator, same message from it ... "to enable 2 step verification for your Google account, please visit accounts.google.com/securityon a computer" ... its already on!

 

[Slug]

This is from memory a couple of months old, so I can't guarantee 100% accuracy.

At the above page, click on "Signing in to Google" on the left, then the > next to "2-Step verification". From here "Primary way you receive codes" should be visible, showing the Authenticator app and Android as active. Next to those should be an option to "Move to a different phone".