At one time, Verizon disabled much of the bluetooth capability (or profiles) in their phones. I think Verizon may have enabled some but not all of the bluetooth profiles in its newer phones. So you might be able to use a bluetooth enabled headset, but you may not be able to transfer files between your Phone and PDA or use your phone's connection to surf the internet - these functions use different profiles. Check with Verizon to see if that is the case with your phone.
If your phone does not show up under the BT Phone Manager in your PDA, you can generally use a default profile to connect your phone and PDA - that's what I did. However, a "Live Update" application should have been included on the CD that came with your PDA. I installed and ran "Live Update" after I had already created a Bluetooth partnership just to see what I was missing and found that now I can find my phone in the drop down list in the BT Phone Manager (big whoop..

...).
If you are able to pair your PDA with your phone, then it is likely that your difficulties are with the phone and not the PDA.
Julie