I have been trying to get Skype to work with my bluetooth headset (it is a Treo Headset) and was having little luck until I found this post on how to configure PC to headset connections

It describes how to configure a dongle (I have the DLink DBT-120) to work with a headset. The problem with most installs is that the Microsoft Bluetooth drivers don’t work with headsets – and they take over the dongle’s drivers if you don’t disable them. The posting gives a good description of the steps to get your headset connected.

Even once it is connected it is a little unwieldy because unlike a phone/headset connection it is in a semi-live mode all the time – which uses up a lot of battery power. So you need to connect/disconnect to the headset when you are not using it to conserve power. It is still nice to have when I don’t happen to be carrying a wired headset for the computer.