Yes, so you see I had mentioned I am already signed in on the authenticator on the new device. Consequently have already skipped that note on step one;
On your mobile device, open the Authenticator app, and select Begin recovery. **Important:**Select the Begin recovery link before signing in.
So I need to either be able to select restore somehow, or log out so I can not log in before beginning the recovery process. I hope that makes more sense, now that I've explained further.