Não tenho muita experiência com o bluetooth, mas tentaria garantir que todo o meu software esteja instalado. Este wiki sugere
sudo apt-get install bluez python-gobject python-dbus
sudo apt-get install \
bluetooth blueman \
bluez-hcidump bluewho python-bluez bluez-tools \
brcm-patchram-plus-nexus7
É sugerido por este outro post do askubuntu
Bluetooth não funciona no Ubuntu 13.04
Se o software não consertá-lo, você pode tentar uma das outras soluções nesse fórum ou consultar o wiki.