1) Versão do Ubuntu ? (ambiente, sabor?)
2) Qual kernel?
uname -a
3) Informar qual é o seu equipamento eventualmente pode ajudar a encontrar uma solução (cpu, ram, gpu, motherboard), marca e modelo se existirem.
4) Assegure-se de que seu sistema esteja atualizado acionando o "Atualizador de programas" pelo Dash ou então:
sudo apt-get update && sudo apt-get upgrade
5) O Bluetooth pode estar identificado pela porta usb, então faça:
lsusb
copie e cole aqui o resultado para vermos se há detecção e identificação do hardware.
6) Um detalhe: é comum em notebooks o bluetooth ter uma chave de hardware, liga/desliga, on/off, acionada a partir de uma combinação de teclas Fn + F? (efe alguma coisa, F12, F11, etc), a qual precisa estar acionada para que o sistema possa detectar e identificar o dispositivo, também é comum em alguns equipamento que quando se liga aparece uma imagem originada do próprio BIOS, então, antes de fazer o lsusb ligue a chave para ligar o bluetooth. Se ligou e identificou vai aparecer o símbolo típico o bluetooth na barra superior.
Isso posto, execute o comando e cole aqui o resultado:
rfkill list all
7) Se detectou o hardware e apareceu o símbolo na barra superior, click nele e verifique se estão na posição:
Bluetooth ON
Visível ON (por padrão está em OFF)
8 ) Se constatar que o hardware foi identificado, o dispositivo está ligado, porém não apareceu o símbolo na barra superior, então acione o ícone "Configurações do Sistema"/Bluetooth e veja as configurações, incluindo se está marcada a opção "Show Bluetooth status in the menu bar"
9) Se ainda não foi, procure na Central de Programas do Ubuntu e instale o
pacote "Suporte a bluetooth";
10) Finalmente, se ainda não foi, ainda pela lojinha do Ubuntu (Software Center), instale o
"Gerenciador bluetooth Blueman".
11) Enquanto se procura uma solução e como alternativa, veja esse link sugerindo o uso do AirDroid sob uma conexão de rede wi-fi:
http://ubuntuforum-br.org/index.php/topic,116784.msg643252.html#msg643252