Have you spoken with customer service about the issue? I am not certain if it is a phone issue, tower issue or a provisioning problem in the At&t system. If you do call them, do it from a different phone # and have the mobile phone # nearby so they can troubleshoot.
One issue that comes to mind is if the voice mail pilot # is incorrectly setup would create such an issue. Hope you get the issue resolved.
If I'm annoyed and you're annoyed, does that make us a paranoid ??
Sarcasm is a fine art...
"Don't believe everything you think"
It's not a matter of if you win or lose, it's how you assign the blame