Eu enfrentei o mesmo erro. No padrão ubuntu desktop bluetooth estava funcionando perfeitamente. Então, no xubuntu, eu removi o blueman (que é o atual gerenciador de bluetooth do xubuntu 12.04) e instalei o gnome-bluetooth. Após a reinicialização, o gerenciador do bluetooth do gnome estava presente no painel superior. Funcionou perfeitamente. Eu acho que há um bug nos pacotes blueman.