If you have a Verizon Wireless Blackberry 7250, you need to run...not walk...to the Verizon Wireless website to download the new 4.1 firmware. It completely resolves the difficulties with bluetooth headsets and these Blackberries. My first headset (an Allways) worked great, until it broke. The second (Scala 500) and third (Plantronics 640) had been disasters. After a week of messing with each, I had given up and gone back to a wired headset.
Then on Monday I was looking at some 7250 forums and discovered complaints about almost every single headset imaginable with the 7250. Meaning the problem was the 7250. Whose new firmware had come out last Friday. It actually took 3+ hours for the upgrade (1:45 for the upgrade, another 1:30+ for enterprise activation). But it was well worth it and can be mostly ignored during that timeframe.
I am now back in love with my 7250.