Do you have your recovery key? When you first setup two factor authentication, they recommend that you save it.
With this code you can setup the authenticator app on your new phone (you can select if you want to use a QR code or the key string).
Otherwise log in with your old phone and reenable the two factor authentication.
I didn't save the key. But my old phone was at my house last night, so I called my mum from my girlfriends house (which is 50 miles away from home) and asked her to give the code from the authenticator app. Bit that didn't work. Is it possible your phone needs to be at the same place instead of further away from the place where you log in?
No, it can be anywhere in the world, as long as the phone's time isn't wrong... You do know such a code only works for a couple of seconds, right?
If your phone's clock is off for 10 seconds, and the website's timestamp is wrong 5 seconds in the opposite direction, you only have a 15 second gap for your mom to tell you the code over the phone before it becomes invalid.
