I've been using Skype 2.1beta for Linux with my bluetooth headset and quality of the sound is just awful. But not always though, if I call echo service, quality is acceptable, but when I call real people there's echo, sound is crippling, there's pauses, voice is unrecognizable, all sorts of quality problems in one call. If I use newest Skype under WIndows with the same headset to call to the same people, quality is more than normal.

So, is there some settings I can tweak, like tell Skype which codec to use or maybe there's noise cancellation plugin for PulseAudio I can use or any other system setting I can try to play with?