iPhone 4: Visual Voicemail asks to be 'set up now' after each reboot

I too am confronted with this issue.
My guess is that many more reports will come flying in once everybody updates their iPhone iOS (which reboots the phone, and thus presents this visual voice mail set-up issue once more). I've avoided it by simply not turning off the phone, and just charging it while on, when the battery needs it.
However, as of last night's update, the phone is incapable of connecting with my service in order to set up visual voice mail - which I've now tried to do 10 times. So, as of last night's iOS update, visual voice mail is unavailable. I can still connect to my voice mail account the old way, by dialling in, and entering my passcode, but I'm PAYING for visual voice mail, you know? I'm definitely going to call Applecare, and will post any useful solutions.
By the way, there are threads in the forums detailing a solution which involves resetting the whole phone (erasing everything), and starting from scratch which allegedly fixes this, but that seems pretty ludicrous to me. What happens when you reboot the phone the next time?
I'm in Toronto, and am with Fido.
-Mark.

Which carrier are you with? I'm with Rogers and currently experiencing the same issue every time I reboot the iPhone 4 it asks to set-up visual voicemail. Though when I call my voicemail manually I can hear my custom greeting and messages but my iPhone believes the visual voicemail is not yet set-up. I filed a bug report with Apple as I don't believe this is a carrier issue. Suggest anyone experiencing the same issue file a bug report with Apple here http://www.apple.com/feedback/iphone.html Choose "Bug Report" in the drop down menu selection for feedback type.

The fix:
Okay, I spoke with Apple Customer Support, and this is the detailed fix for the constant visual voicemail re-set after rebooting the iPhone (4). A warning though, it's going to use up a lot of your time!
1. Make sure that you've synched your iPhone, and have a computer back up (which includes all of your contacts, apps, email, photos, etc. - EVERYTHING.
2. Reset your iPhone 4 back to the factory default (this erases EVERYTHING from your iPhone). This is the "Restore" option found on the "Summary" tab in iTunes when your iPhone 4 is selected.
3. After step 2 is complete, when you are given the option to restore the iPhone either from a back-up, or start as a new iPhone, choose the new iPhone option (it's possible that your back-up has a "corruption" which lead to this problem).
4. Re-synch, and re-add all of your apps, movies, books, and photos, etc. You will have to redo any folders that you may have made (pain!).
5. You may have to update the phone's carrier settings (remember when you first got the phone?), by pressing a prompt on the phone if it tells you that a carrier update is available (download the update). The phone will also prompt you with the fact that it's now registered (with your carrier). This only takes a second (the shortest part of the whole process). Your visual voice mail should work. Your greeting may be set to "default", but if you choose "custom", your greeting should be there (push "play" to make sure). If not, then record a new one. My greeting was still there, and I didn't have to re-enter my password. All of my old messages were still there, too. Success!
6. You'll have to re-enter your wi-fi password in order to re-enable wi-fi.
7. You're done. It works. I've tested it, by restarting (re-booting) the iPhone 4 several times.
8. Go to bed, because it's late!
You're welcome!
-Mark.

Mark, Id like to thank you for your time and effort! I have yet to try the process - I have to find the time first! - But you've provided some much needed insight.

Thanks!

I'd like to thank you Mark.
Your post fixed the same issue on my phone.

Sadly, it didn't solve the problem for me. But there's a variation or two with my situation that may explain it.

I got my device from Apple. When they sent it to me they configured it for my carrier - Rogers.

A couple of months later I moved to a new province. When I got a new phone number I restarted my device and that's when I noticed a few changes: when I go into Settings > Carrier I have all three Canadian providers listed (Rogers, TELUS, Bell). Because the phone sets itself to Automatic, whenever I'm in a low signal area it starts searching for a connection using the other provider options. I can select the option for my provider but it doesn't 'stick'.

It's those low-signal moments - and every instance of restarting my phone - that cause my voicemail settings to be lost.

Any thoughts? This is making me nuts.

I've just tried Resetting All Settings. I could just reboot the phone to find out if it worked but I think I'd scream if it didn't.

I'll be back if this doesn't work. 😉

Hi, My husbands visual voicemail was doing this. I tried resetting Network Settings but it didnt work so last night I tried resetting ALL settings and it worked. I had to re do things like alarms and wallpapers and ringtones but it was worth it to get voicmail back instead of the red dot of death