I had the same problem and just called customer service. They provided me with the voicemail access number for my area which I keyed in at (on Nokia 2610) MESSAGING -> VOICE MESSAGES -> VOICE MAIL NUMBER. Now I can press and hold "1" and I'm prompted for my voicemail password.
I'm in Victoria, so the access number for this area (and Vancouver) is 1.604.762.9993. You need to prefix the number with '**' typed quickly so it produces a '+'. While 604 area codes are generally long distance from Victoria, I'm not charged LongDistance on this number. The only charge is the standard $.20 charge.