Para o Ubuntu 14.04, 15.04 e 15.10, isso pode ser corrigido por um módulo personalizado. Eu enviei um patch upstream e ele será corrigido nos kernels oficiais em algum momento.
Agora você pode instalar o módulo executando
sudo add-apt-repository ppa:hanipouspilot/bluetooth
sudo apt-get update
sudo apt-get install btusb-lp1506615-dkms
Depois de instalar o módulo, desligue o laptop e não apenas reinicialize. Depois disso, o bluetooth deve funcionar.
Também faz sentido ativar a coexistência sem fio e sem fio executando:
sudo tee /etc/modprobe.d/ath9k.conf <<< "options ath9k btcoex_enable=1"
Isso consertará atrasos ou desconexões ao usar o Wi-Fi e o bluetooth ao mesmo tempo. Será aplicado após a reinicialização.