I've got a Bluetooth headset which works great in both Windows 8 and Android 4.2 however on Ubuntu (13.10) it just doesn't seem to work. I installed Blueman, it paired and connected successfully when I tried Audio sink but it still doesn't show up in my Sound Settings nor PulseAudio which I installed and tried. All there is in my Sound Settings is "Analog Output". I tried several fix like changing and adding things in /etc/bluetooth/audio.conf without any success. I've restarted the bluetooth service several times in the process as well.
Let me know if you need more information from me and my system.
Kind regards, Michael.