Verifique seu log do dmesg:
dmesg | grep -i blue
No meu caso, tive um problema com a falta de firmware:
$ dmesg | grep -i blue
[ 2.216624] Bluetooth: Core ver 2.18
[ 2.216639] Bluetooth: HCI device and connection manager initialized
[ 2.216644] Bluetooth: HCI socket layer initialized
[ 2.216646] Bluetooth: L2CAP socket layer initialized
[ 2.216653] Bluetooth: SCO socket layer initialized
[ 2.237027] Bluetooth: Firmware file "ath3k-1.fw" not found
[ 2.414454] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[ 2.414457] Bluetooth: BNEP filters: protocol multicast
[ 2.414464] Bluetooth: BNEP socket layer initialized
[ 2.419758] Bluetooth: RFCOMM TTY layer initialized
[ 2.419767] Bluetooth: RFCOMM socket layer initialized
[ 2.419772] Bluetooth: RFCOMM ver 1.11
Isso foi resolvido por:
sudo apt-get install linux-firmware
Espero que isso seja útil.