This happened to me on my droid last week. I spoke to a tier 2 tech from verizon and he suggested doing this:
1. Take out the battery with the phone ON.
2. Wait 5 minutes, put the battery back in and POWER ON.
3. (for verizon) Dial *228 and update roaming capabilities (this is option 2 on the automated machine)
4. DONE!
He suggested that if that does not work, back up all your settings, then do a full system reset
Settings > Privacy > Factory Data Reset
and if that does not work, it's the phone that is the problem, not the network.
Again, this is for my DROID
Or skip all that and he can just pay his bill on time. If we want to have nice things (like the Droid), there's a price attached.