This happened to me when I changed carriers. After interacting with UA support and confirming everything was set correctly with the phone number, we decided to just wait it out. It solved itself in about a week.

Their system must use what it has learned about carrier attachment to a number. I can also see it screwing up royally if you move from iOS to Android - which is always a challenge because of iMessage.