Going to follow this thread since my iPhone seems to have caught the Visual Voicemail bug. Hopefully AT&T or Apple figures this out soon :-/
- From the home screen go to "Phone > Visual Voicemail".
- Remove all of your items from "Deleted Messages".
- You should see a "Deleted Messages" folder. Go to it and choose "Clear All" and yes to confirm.
- Call your phone's voice number, it will give you the voicemail prompt (if you have a password setup, it will ask for it now.)
- Choose "Personal Options" (#4).
- Choose "Administrative Options" (#2).
- Choose passwords and enter a new password.
- Return to the main menu and then end the call.
- Back on your phone's home screen choose "General > Settings > Reset > Reset Network Settings". *FYI this will revert any saved Wi-Fi passwords and return Wi-Fi settings to their default state.
- Congratulations - upon reboot you should begin receiving Visual Voicemails and any related badges on your Phone icon.