Tive um problema semelhante, mas na verdade a solução que você identificou está de fato funcionando. Para que o Ubuntu detecte seu dispositivo, você deve certificar-se de que este último está em modo de pareamento com o bluetooth do pc desligado. Quando o dispositivo entrar no modo de pareamento, você ativará o bluetooh e o dispositivo aparecerá na lista.