Do you have any third party Voicemail apps installed? Are you using Visual Voicemail? If no to both, press and hold the 1 key. You should be taken to your voicemail. If not dial your phone number from another phone, decline the call and press the star key. This should allow you to at least see if your inbox has been setup correctly. Could also be a provisioning error.
The problem was Visual Voicemail was apparently engaged. I switched the plan on my wife's BlackBerry last week and for some reason audio voicemail was dropped and Visual Voicemail enabled. I was able to cure this via Verizon and now have the audio voicemail functionality back!