I went to "level 2" support with Verizon on the phone and they said that they had to "reset the information for my phone on the switch" (or some such thing). I would continue to bug them and make sure that it is not a problem on their end. Your phone may be just fine.
I told them what you said and they replied via email, "We reviewed your account setup and refreshed your location details via the network. This allows your account selections and settings to be refreshed for network access."
It's working for now but I'll give it a couple of days before I say it's fixed because it goes in and out. Anyway, thanks for the suggestion and hope it fixes my problem!