I'm using Google Voice happily on my iPhone. I haven't used AT&T's Visual Voicemail, so I can't really compare the two, though.
As others have mentioned, the transcription isn't great, but I can almost always get the gist of the message, often more.
Since I saved Google Voice as a home-screen shortcut, it's pretty easy to access messages.
I also have GV set to e-mail me about new voice messages, and email set to forward those notices to
Nuage, a helpful app/service that provides a push notification.
If you make the switch, I recommend going into advanced settings for your mobile number and choosing: "When someone calls this phone directly and I don't pick up... Go straight to voicemail." Otherwise, callers hear ringing for way too long before GV takes a message.