Hi guys,
I couldn't pair either of my two headsets to my Windows 7 machine. Here's what fixed it for me. In Device Manager, under Bluetooth Radios, I opened the properties for my radio (Broadcom 2046 Bluetooth 2.1+EDR USB Device with First Connect). Under the Advanced tab, I took the hyphen out of my radio's name. The headsets paired immediately after that.
This is a pretty serious bug considering the radio takes its name from the computer name, which is username-PC by default when you install Windows 7.
I hope this solves your problems.
Note that in order to actually use the headset, you will probably have to update your Bluetooth drivers if you haven't done so already. Go to http://www.broadcom.com/support/bluetooth/update.php