Tanto quanto me lembro, tive o mesmo problema.
Não me lembro se podia ou não ver meu laptop em meu dispositivo móvel, mas lembro de ter alguns problemas de conectividade.
O que funcionou para mim foi instalar o "Bluetooth Manager". Isso resolveu meus problemas.
Eu acho que você instala este aplicativo com o comando: sudo apt-get install blueman
.
Espero que isso ajude ...