This exact thing happened to me today as well. After waiting a few hours I've regained access to the account but can't change the recovery phone number because to get into that settings panel it requires me to verify it... with the old phone number.
I lost my Skype account the same way. I had been using it normally when suddenly one day it automatically logged me out, then when I logged in with the correct password it insisted on sending a code to a phone number that I have long lost.