First I'll say I'm nowhere near an expert on bluetooth with Ubuntu - or even bluetooth for that matter. What I've done is mash together a lot of different things until I found what worked for me. Your mileage my vary, but this is how I got my Plantronics bluetooth cellphone headset working with Skype in 64 bit Ubuntu Intrepid.

Please note - the bluetooth stack changed between Hardy (8.04) and Intrepid (8.10). This is for Intrepid.

Setup the bluetooth environment

First, of course, you must get bluetooth working and paired with your bluetooth headset. That part is actually pretty easy.

Make sure you have the following packages. I think bluez-alsa is the one that may not be installed by default, but go ahead and check them all:

sudo apt-get install bluetooth bluez bluez-gnome bluez-alsa bluez-gstreamer libbluetooth3

Once it's all installed, create a file called .asoundrc in your home directory and place the following text inside it:

pcm.Headset {
  type bluetooth
  profile "voice"
}

I saw several HOWTO's that talked about loading modules or otherwise affecting the audio drivers, but I found that with Intrepid, none of that was necessary.

Pairing your headset