I think I have resolved my problem and you are not going to believe how. This was the direction I received from a VZW Data Tech (Thank you VZW):
Delete pairing
Hard Reset (Turn Off, Remove Battery, Turn On)
When you go to do the pairing make sure the bluetooth headset is at least 4or 5 feet apart from the blackberry (I had previously done it with them just inches apart from each other during the pairing).
I did this and my bluetooth is now remaining connected all the time.
Apparently when you pair, the distance is factored in to what drives subsequent connections between the blackberry and the handset.
Hope this helps you as well!