After traveling in Europe for three weeks and having data roaming off, I had this issue as well. I tried a number of different solutions that I found on the Internet, but ultimately I was able to finally get it resolved after spending time on the phone with the ATT support tech. The problem seemed to be that the iPhone "forgot" what the features were to access voicemail. Here's what we did:
1. Go to Settings->General->Reset and reset the network settings. The phone will restart.
2. Go to the Phone and open the dialpad. Type in the following sequence on the iPhone and hit the CALL button.
*5005*86*8622513567#
3. After you hit the CALL button you will notice the screen flashes. 🙂
4. That's it.
After implementing these steps, visual voicemail popped up and worked right away on both 3G and 2G.
Alen