Have you tried another headset?
Often the limiting facor is not the headset, but the computer (or other device). The computer may have Bluetooth capability, but it may be for file sharing or printing, and not for sound/headset use. There are several different "modules" that a programmer/deigner can incorporate into the Bluetooth service on the computer.
Also, I definitely could be the driver...so perhaps the BlueSoleil install could help...though personally, I find that software to be lacking.
I posted a discussion of Bluetooth and compatibility of devices on my blog the other day. You can read it at
http://blog.wickedgoodtech.com. (I just started the site and blog, so there isn't much info there yet).
cheers