You may need to set up your voicemail number on the phone. I had to manually enter the voicemail number (the number called to access my voicemail inbox) on my Lumia 920 when I first got it. You can find the voicemail number in your old phone's settings. In your Lumia, go to "Settings", "Applications", "Phone", and you should be able to enter your voicemail number in there.
After that, when your the visual voicemail prompt returns, you can enter your password for your voicemail inbox, or if you don't have one, just hit "enter" and you should be good to go.