Como cada GNU/Linux (y cada versión) sale del horno con su propia receta, lo que en una ocasión nos viene de serie y configurado en otras nos puede incluso costar encontrar la manera de instalarlo.
El último Ubuntu nos llega con Bluetooth a medias: algunas utilidades y librerías sí, otras no. Por ejemplo, no trae el paquete gnome-bluetooth, que es justamente el más importante y el que crea un atajo gráfico (Aplicaciones/ Accesorios/ Compartición de archivos por Bluetooth) en el menú del sistema.
Pero tampoco te deja instalarlo: no lo encuentra.
Si quieres activar Bluetooth necesitas modificar el archivo sources.list a fin de añadir los repositorios backport, que vienen comentados. Basta descomentarlos y actualizar la lista:
1. sudo gedit /etc/apt/sources.list
2. Descomentar los dos repositorios que hacen referencia a los backports
3. sudo apt-get update
4. sudo apt-get install gnome-bluetooth
Esta orden te instalará además libbtctl4, libgnomebt0 y libopenobex1