The Plantronics M165 Marque 2 Bluetooth headset paired very nicely with my Android phone. To pair it to my computer running Linux Mint 17 I:
  1. Clicked on the Bluetooth icon
  2. Turned on Bluetooth
  3. Clicked “Set up a new device…”
  4. Pressed and held the Call button on the headset for five or six seconds, until the computer found the headset (the Plantronics documentation is here)
The sound test in the Sound Settings dialogue didn’t sound right, but I could play music through the headset and it sounded recognizable.
Using it with Skype gave super-sucky sound quality. Lowering the PCM level in alsamixer to about 70 made the sound quality a lot better, but still not great (lowering the PCM level was suggested here).
alsamixer is a command-line application. Open a Terminal and type: alsamixer, then use the left and right arrow keys to find “PCM”, and use the up and down arrow keys to set the level.
Still trying to improve the sound quality, I noticed that the built-in microphone is on when the headset is on. On a Skype test call, manually turning off the microphone didn’t seem to make a lot of difference to the sound quality.
Using Audacity to record sound, the quality of the built-in microphone was even worse than the headset.
[Edit] Using the headset, I made a Skype call to my son, and he said the quality of my voice was okay. I could also hear him okay.
In case you need to know, the Bluetooth config files are in /etc/bluetooth.