The visual voicemail is different than dialing into the voicemail - allows user to directly go to a specific voicemail, without having to dial in, skip the messages till we get to the correct message.
For Visual voicemail, go to the phone app - settings/calls/voicemail, and enable "Visual Voicemail" - see if that helps.