Desde la terminal esriben:

sudo apt-get install bluetooth bluez bluez alsa(en el caso no tengan como predeterminado el soporte, generalmente todos lo tienen)

sudo apt-get install gnome-bluetooth (herrmienta que no es por defecto para bluetooth)

Aplicaciones > Accesorios > Compartir archivos por bluetooth

Sistema > Preferencias > Bluetooth

Click derecho en el ícono de bluetooth y elegir preferencias... Elegir Siempre visible, luego el signo más para agregar dispositivos bluetooth..siguiente... siguiente.. hasta encontrarlo.. así debe de quedar!

Es necesario siempre realizar el paso 3 antes de querer conectarse con algún dispositivo... ojalá les sirva..

(*) gracias por la corrección bushwaca, era bluetooth obviamente, no wine.. tremendo error!