my iPhone 3G actually did this last night as well and I was very confused. I ended up letting it call the voicemail and listened to it for a few minutes then hung up. I then closed the phone app and relaunched it, clicked around the bottom buttons and went back to voicemail and it lagged for a second and prompted me for my voicemail password, then loaded visual voicemail. the last few times I've tried it, it loads fine, so I'm not sure what the hiccup was.