I have a Plantronics 510. It pairs properly with the computer, but I can't get audio to actually work. I upgraded to the bluez package from Baptiste Mille-Mathias's PPA, though I had to rebuild it after updating debian/rules. See my PPA for details. I also upgraded the pulseaudio stuff from themuso's PPA.
When I run this, it thinks about working and then eventually times out:
pactl load-module module-bluetooth-device sink_name="bluetooth" address="00:19:7F:DC:AB:5B"