I read something where you could be outside AT&T's Edge Network
Apparently other carriers have Edge network as well, and I read in the Apple literature you could actually end up roaming, and get charged for Roaming. I'd call your AT&T or Apple dealer and see if they have any info.
this has happened to me before when I had a blackberry. Whenever it did that it always had something to do with my data plan being screwed up. As a matter of fact im having problems right now so my guess is it has something to do with switching from the bb plan to the iPhone plan.
Just out of curiosity does your visual voicemail work right or when you press the vm button does it go straight to vm?
Since att customer service is closed tomorrow going up to the store.