Well, something similar happened to me as well. I moved (just a few kilometres, too). In fact, it happens in about half of the cases when I'm logging in in some new location.

I want to log in (to Youtube or whatever) from the machine and the browser I always use, just from a different IP. Then I get asked for a phone number (any phone number) to verify that it's me[1], which in itself is a nonsense. That "another way to sign in" includes asking me for a date when that account was created (what???) and sending a code to email, which sometimes works, sometimes it does not.

I mean, when I was moving, I fully expected to never be able to get my account. What an utterly rubbish service. And people actually put significant amount of money to it?

[1] https://puu.sh/rrKyG/678746a09e.png

Edit: And how do you "call a rep" anyway? I haven't seen anything even remotely resembling live support, i.e. one that isn't community-based or self-service.