After upgrading my iPhone to iOS4, I did run into a problem with my voicemail. Attempting to access the Voicemail tab would cause an endless series of Password prompts. I tried several different passwords I thought it might be, but none of them worked. In the end, I ended up calling my number, jumping into voicemail, setting a new password, and then entering it on my phone.
It looks like the same thing happened to people last year. Carl had the same problem on both of their phones.
