I've got an original iphone that is unlocked with a pay as you go plan, no data plan. According to Fido's instructions you can press 1 on the keypad and that will let you setup the voicemail, but that is not working for me. I do have data disabled in an APN. I'm under the impression you can only setup voicemail on the phone the plan is on.
***Edited to add labels***
Solved! Go to Solution.