I know because the messages on my NEW phone that I am trying to set up state "We sent this to (your old phone -- identified by type of phone, which is different from the model I am setting up).
See if you can revert to SMS verification through some option at login. I can't verify it now, but the choice could be accessible though something non-obvious like "I'm having problems verifying". Make sure it's trying to use a text message instead of some other method... and let's hope you have it configured.