There's a new SMS region policy in the Authentication > Settings section of Firebase. Now you have to enable and select regions where SMS is allowed. I was experiencing the same thing as you, and just now came across this.