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 .
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.
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.
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.
 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.