used to happen alot with my blackberry, all i would do is turn it off, take out the battery for a second and turn it back on, ive had it happen to me once on my evo but it started working again after an hour or so
It should only happen when you are roaming. If it is bothering hou that much you can turn roaming off on your phone and it will fix the problem. Funny thing is that I haven't had that issue with any other type of device other than an HTC phone on Sprint.