I had a lot of problems with my Visual Voicemail as well.
So far I have found this feature to be nothing but problems. Sure it works and I guess it's nice you don't have to call ATT and listen there, but I don't think this feature should have been played so big.