Try opening the phone app and pressing and holding the "1" key. That should place you in your cellular carrier's voicemail. Perhaps from there you will find it easier to set up your visual voicemail.
If you continue to have issues, ask your cellular carrier for assistance.
Enjoy your new iPhone!