You may have to call Apple; 1-800-MYIPHONE
I had a similar issue; my Voicemail button would not go active, letting me access the Visual Voicemail section.
Apple walked me through some steps that got it working.
Go to you VoiceMail, it will dial. Change your Voicemail Password to what you desire. End call and enter Settings. It should ask for you voicemail password in a popup. From there it should start to work.