Several users who have updated to iOS 4.1 report the sudden appearance of several visual voicemail messages dating back several weeks. The update apparently fixes a visual voicemail bug that caused failure of some or all messages to appear.
So if you think you’re missing some messages, try the update. If you’re still not receiving all visual voicemails, try these fixes:
Call voicemail (try this first). In some cases, this issue can be resolved by simply dialing your own number to manually access voicemail, at which point you may be prompted for your voicemail password. After entering your password, visual voicemail messages may appear.
Reset password on AT&T website (try this next). Log in to your myWireless Account and select My Services. Then choose the Reset Voicemail Password link from the right column under Phone/Device Support. After resetting your password, you’ll get a text message with a new password. You should then see a message indicating that your password is wrong, at which point you should enter the new password. Otherwise, tap voicemail and enter the new password.
Restore, but not from backup (try this last). It appears that bad holdover data from iPhone backups (especially those created for previous iPhone models) can cause this issue. Restoring as a new phone will delete contacts and other data, but may resolve the problem. To do so, connect your iPhone or iPod touch to your computer, click “Restore” in iTunes, then choose “setup as new phone.”
Some incidences of this issue may require a DFU restore.
Nicholas on 
Lawrence Alonzo on 
rickyc on 
Carnghamcats on 
Deb Santagata on 
MARK on 
Shafqat Zaman on 
AppleID:( on 
September 14, 2010 at 11:24 AM
jeesh, no kidding, i just updated and THREE DOZEN vmails from the last 3 weeks were suddenly ‘delivered.’
what the &*( ?!?!?
September 23, 2010 at 12:11 AM
Same here! I had 25 or so messages over the past few weeks that I never knew about. Even a job offer!
I’m super pissed at this one… and to think Apple didn’t notify it’s customers?
Just send out a mess of apologies to people for not responding to them.
!!!
October 6, 2010 at 11:10 PM
Try steps one and two, but before you go and restore your phone you go to Settings/General/Reset and Reset All Settings. I found this fix on another website and it worked for my phone! Unfortunately, I did loose all my saved visual voicemails, but all the voicemails that were trapped on their service and not delivered to my iPhone 3GS did get pushed out as well as all new ones since. I agree with KGC, where’s the heads up on the problem and the fix Apple? I tried customer service and they said they wouldn’t help me until I upgraded from 4.0.1 which I couldn’t do while traveling. Apple, stop treating the customer as if it’s their fault when your software doesn’t work correctly.
October 13, 2010 at 11:33 AM
It refuses to take the password. It claims it can’t update at this time, try again later.
This is bullsh*t. I frucking hate Apple/AT&T.
The last update I got showed me some new messages that I didn’t know about. I had to start apologizing to ppl that I accused of telling tall tales when they said they left me a message.
Ugghhh… I’m dreading calling AT&T support. *Sigh*
October 25, 2010 at 8:37 PM
To Ikhide A
I had the same issue.
Even though you reset password it can still be disabled for your account.
Press and hold 1 – > this should get you to the voice mail.
Follow prompts to actually turn on the password for your voice mail account. I followed 4-> 2->1->2
After you dial to your voice mail again – it will ask you for the password.
At this point you should configure visual voice mail password.
After these steps – it worked for me.
Good luck!
December 15, 2010 at 6:49 PM
I Was same problem I don’t what I install something wrong When restore sure All anything work but after install install forget to check that it