Enviei um patch upstream. Daqui a pouco, este dispositivo será suportado pelos kernels do Ubuntu.
Enquanto isso, uma solução alternativa pode ser usada. Instale um pacote dkms com este patch:
wget https://launchpad.net/~hanipouspilot/+archive/ubuntu/bluetooth/+files/btusb-lp1542564-dkms_0.2_all.deb
sudo dpkg -i btusb-lp1542564-dkms_0.2_all.deb
e reinicie.
Se o bluetooth ainda não funcionar, ele precisa de algum firmware que ainda não esteja incluído no Ubuntu. Pode ser instalado por:
wget http://download.windowsupdate.com/d/msdownload/update/driver/drvs/2014/01/20623393_919a4673931aa789f0b1c3eeafb360b36097894a.cab
sudo cabextract 20623393_919a4673931aa789f0b1c3eeafb360b36097894a.cab -F *.dfu -d /lib/firmware/ar3k
Obrigado a Jeremy31 pelo link e pelo comando.