I don't think Verizon's contact backup feature works with BlackBerry's, if I remember right.
Do you have you contacts stored somewhere else, like Microsoft Outlook? If so, just like x12 said, you can use the desktop manager to sync your contacts with your Outlook to your new BlackBerry.
If not and you still have your old phone, try stopping a Verizon store. Usually, they can transfer your contacts from an old phone to a new one with their software.
Don't worry, you will soon find out why people call them "crackberry's" once you get the kinks worked out and get used to it.
