Eu tive o mesmo problema quando fiz uma atualização para o Ubuntu 11.10. Hoje resolvi o problema.
Só tive que instalar blueman assim:
sudo apt-get install blueman
Resolvido, o ícone do bluetooth agora está de volta à barra superior da unidade.