Bluetooth sound worked perfectly for me in Ubuntu 10.04. I recently upgraded to 11.10, and although sound in general works fine, Bluetooth sound almost never works. My headset is paired, and Sound Settings shows it's selected as the output device, but no sound is being output. I've tested the headset with other devices, and confirmed it still works, so the issue is definitely with 11.10.

I'm not seeing any explicit errors and I can't find any similar issues with 11.10 through Google. I tried restarting the bluetooth service, but that had no effect. What can I do to fix this?