Just wanted to add to the community knowledge. After upgrading, every time I went to Phone > Voicemail it would dial voicemail, not show me the visual voicemail. Upgrading to iOS 4 erases your password (apparently) so you have to get the phone to prompt you for your 4-digit password.
I accomplished this by going to Settings -> Sounds.
First, this problem seems to affect those of us who, at one time or another, jailbroke our iPhones. (C'mon, admit it.) If you truly never jailbroke your phone, you may be experiencing a different problem with a different solution.
So here's what you need to do:
BE SURE TO SYNC AND BACK UP YOUR PHONE (with iTunes) BEFORE YOU PROCEED FURTHER.
1. Put your phone into DFU mode (do a google search to find the details on how to do this, it's easy.)
2. Launch iTunes, if it wasn't already running, connect your phone to your computer via USB, then when iTunes ask if you want to restore your phone to factory settings, choose that option.
3. After the restore to factory settings is complete, test the voicemail, your messages should appear (you may need to enter your voicemail password.)
4. Assuming that works, you can now use iTunes to restore your phone from the backup you made before starting this procedure. When that long process is done, you should be back to normal.
And remember all of this the next time you think about jailbreaking, lol...
This is the only solution that worked for me. I also had jailbroken iPhone. I tried all the solutions before I spend 30 minutes with AT&T customer support and 30 minutes with an Apple Genius. I showed him this solution, he agreed to do it and all was solved.
CORRECTION! It worked until I restored all my backed up data, contacts, apps, music, etc. Then all my voice mail were gone again with Visual Voicemail unavailable again. ***?
3G network came back right away on mine didn't even have to reboot. Just had the visual voicemail disappear which was resolved by the process I wrote the instructions on.
I had no 3G service at all. It kept wanting me to connect to wifi for everything. After 45 minutes on the phone with support, they had me restore my phone but as a new phone, not restore from backup. After that my 3G worked again. If you do the restore as a new phone, make sure to save your contacts in outlook or windows contacts so you don't lose them. I also made sure to save all my pictures onto my computer so I didn't lose them either. Good Luck!
This is the solution that finally worked for me. At first Visual Voicemail did not come up. But after a few minutes it did! There is something funny about a phone that has been j-bkn (they won't let you use the word in the forums) that messes up the Visual Voicemail with the 4.0 install.
This worked for me, thanks! None of the AT&T defaults or last 4 SSN or last 4 of phone number worked. Calling 611 and following the prompts was very simple and straight forward. The temp password came through almost instantly.
This is definitely NOT unique to jailbr*ken phones. Neither my wife's nor mine have ever left the "ranch", but we both got bit by the new, mystery voicemail password with IOS4 upgrades on our 3GS's.
I logged into my wireless.att.com account and found the password reset form under voicemail help. That reset and sent me a quick text with a temp password.
Then I found the instructions on how to get to AT&T's regular voicemail system by holding "1" on the phone keypad. Then I surfed into the voicemail options and disabled the password altogether.
And I did have to record a new custom greeting message.
I think this little snafu rests squarely with AT&T again.
My week old iPhone 4 when not on a Wifi connection will not hold the 3G or Edge connection. I have tried everything including replacing the sim card. When it does connect, it doesn't take long (minutes) before my voicemail is unavailable and it shows No Service. I never had this issue with my old iPhone 3G. Funny thing is that another iPhone 4 in my house, doesn't appear to be having these issues.
The solution is EASY. General Settings->Reset-?Reset All Settings. You won't lose anything, just WiFi password. Fixes the Voice Mail problem. Try it. Got the fix from another Google post, and it fixed it for everyone.