Go to the AT&T web site, log in, and under Phone, Device Support you'll see an option to 'Reset Voicemail Password.' Go ahead and do that, and AT&T will send you a text message with a temporary password. Go to your iPhone, set up Visual Voicemail again as if your phone was new, and put your old password back in.
It seems like AT&T could handle all this automatically, and it clearly works for some, but a quick check of friends who upgraded found quite a few with the problem. All this logging in and re-setting passwords is not the most elegant solution, but apparently it is the only solution.
Hope this helps some of you.