When iPhone AT&T visual voice mail has disappeared and change voicemail password is stuck on "saving password"

I'm used to running into odd problems when I upgrade our iPhones, but Emily's Voicemail malfunction was particularly odd. I do wonder how civilians cope with this stuff [1].

I'd swapped the SIM that came with a 5S I pinched into my former 5 then did a restore from Emily's 4S backup. It had the usual restore quirks -- need to sync twice, entering iCloud credentials multiple times (".me" confusion?), etc. 

The worst was voicemail though. When I checked there was no visual voicemail, just a call to AT&T's old school stuff. Apple's troubleshooting guide didn't work -- including a network settings reset. I reset her voice mail password from the AT&T mobile web site -- that didn't work either. When I tried a reset from the i5 it hung on "saving password".

What seemed to work was a whacky recommendation I've seen in a couple of places.

When I try to setup a greeting for my...: Apple Support Communities

had this problem, and it has stopped. I am not sure if this will work for you, but it worked for me. Call your own number--you should get a prompt to enter your password. Follow the phone tree prompts to personal options. Record and save a new personal greeting. After I did this, and went back to my iPhone visual voicemail screen, I got a new message that said your voicemail password is wrong. I reentered my voicemail PIN and then the save button started working again. Hope this works for you.

 Lost your Visual Voice mail? - MacRumors Forums

I let the direct voicemail call go through, entered my password AND RERECORDED MY GREETING USING THE 3RD OPTION OF FULL PERSONAL GREETING. My iPhone then prompted me with a message saying I had the wrong voicemail password. I entered the password and Visual Voicemail re activated.  

It felt like voodoo, but I had nothing to lose so I looked up the voice mail commands and tried. A minute or so after I disconnected a dialog popped up asking me to enter a voicemail password. I did that and Visual Voicemail returned.

I'm not sure the "magical" fix really did anything. Maybe AT&T's system just took a while to reset. Perhaps if I'd turned the phone on/off a few more times, or just waited, it would have fixed itself. Still, if you get stuck, you might as well try this one.

[1] Maybe it's this kind of thing that causes otherwise rational economists to confuse the cost of replacing a battery on a 4yo phone with the subsidy price of a new device (Rampell seems to have revised her post to cover her confusion).

Update 11/30/2013: This happened to another phone, again with a SIM swap. I wonder if the problem is more common on 7.0.3. This time changing the voice greeting had no effect, but resetting network settings brought up a password prompt and fixed the problem. I only had to reenter the wifi password.