I have the Plantronics Discovery 655 and it's amazing. There is a Blackberry branded one coming out on the 27th that fixes a few of the bugs (for $40 more, see
BlackBerry -> accessories) The comfort and sound are amazing. I've owned only Motorola Bluetooth HS's in the past, so those are what I'm basing my recommendation on.