When you call your voicemail for the first time, it should give you instructions for what to do. Usually, your first password is the last four digits of your phone number.
I would try calling your cell phone provider. They would be able to reset your password and then you can go back in and change it to whatever you would like.
If you BB is not a brand new line for you, meaning you had a different phone with the same phone number with the same carrier, your password will be the same as it was with your old phone. Hope this helps!
Posted from my CrackBerry at wapforums.crackberry.com