I bought an USB Bluetooth key (Belkin - F8T013), which works fine, immediately after connexion.
Nothing to do, really, not even a "bluetooth restart"...

Here some clues, maybe !
damien@vostro:~$ lsmod | grep bluetooth
bluetooth              61924  23 btusb,sco,bnep,rfcomm,l2cap
             ==> before having that key, I had no 'btusb'
damien@vostro:~$ dmesg | grep 'Bluetooth'
[   32.211975] Bluetooth: Core ver 2.13
[   32.214162] Bluetooth: HCI device and connection manager initialized
[   32.214169] Bluetooth: HCI socket layer initialized
[   32.264247] Bluetooth: L2CAP ver 2.11
[   32.264260] Bluetooth: L2CAP socket layer initialized
[   32.331217] Bluetooth: RFCOMM socket layer initialized
[   32.331243] Bluetooth: RFCOMM TTY layer initialized
[   32.331248] Bluetooth: RFCOMM ver 1.10
[   32.365798] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[   32.365813] Bluetooth: BNEP filters: protocol multicast
[   32.637959] Bluetooth: SCO (Voice Link) ver 0.6
[   32.637974] Bluetooth: SCO socket layer initialized
[  302.061098] Bluetooth: Generic Bluetooth USB driver ver 0.3
             ==> before having that key, I had not this Generic BT USB driver

before having the key, daemon.log said :
Nov  5 07:20:23 vostro bluetoothd[6656]: Bluetooth daemon
Nov  5 07:20:23 vostro bluetoothd[6656]: Starting SDP server
Nov  5 07:20:23 vostro bluetoothd[6656]: Starting experimental netlink support
Nov  5 07:20:23 vostro bluetoothd[6656]: Failed to find Bluetooth netlink family
Nov  5 07:20:23 vostro bluetoothd[6656]: Can't init plugin /usr/lib/bluetooth/plugins/netlink.so
Nov  5 07:20:23 vostro bluetoothd[6656]: bridge pan0 created
Nov  5 23:51:06 vostro bluetoothd[6656]: bridge pan0 removed
Nov  5 23:51:06 vostro bluetoothd[6656]: Stopping SDP server
Nov  5 23:51:06 vostro bluetoothd[6656]: Exit
Nov  5 23:51:06 vostro bluetoothd[19503]: Bluetooth daemon
Nov  5 23:51:06 vostro bluetoothd[19503]: Starting SDP server
Nov  5 23:51:06 vostro bluetoothd[19503]: Starting experimental netlink support
Nov  5 23:51:06 vostro bluetoothd[19503]: Failed to find Bluetooth netlink family
Nov  5 23:51:06 vostro bluetoothd[19503]: Can't init plugin /usr/lib/bluetooth/plugins/netlink.so
Nov  5 23:51:06 vostro bluetoothd[19503]: bridge pan0 created

Now, it says :
Nov  9 00:44:10 vostro bluetoothd[8416]: HCI dev 0 registered
Nov  9 00:44:10 vostro bluetoothd[8416]: HCI dev 0 up
Nov  9 00:44:10 vostro bluetoothd[8416]: Failed to listen on control channel
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.SerialProxyManager on path /org/bluez/hci0
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.Service on path /org/bluez/hci0
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.NetworkPeer on path /org/bluez/hci0
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.NetworkHub on path /org/bluez/hci0
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.NetworkRouter on path /org/bluez/hci0
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.Serial on path /org/bluez/hci0/dev_MAC_ADRESS1
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.Control on path /org/bluez/hci0/dev_MAC_ADRESS1
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.Serial on path /org/bluez/hci0/dev_MAC_ADRESS2
Nov  9 00:44:10 vostro bluetoothd[8416]: Registered interface org.bluez.Control on path /org/bluez/hci0/dev_MAC_ADRESS2
Nov  9 00:44:10 vostro bluetoothd[8416]: Adapter /org/bluez/hci0 has been enabled
Nov  9 00:44:10 vostro bluetoothd[8416]: Starting security manager 0

hope this help... Please provide requirements if further info needed...
Oh, by the way ! It's a Dell .... 
damien@vostro:~$ sudo getSystemId
Libsmbios:    2.0.3
System ID:    0x0273
Service Tag:  XXXXXX
Express Service Code: YYYYYYYYY
Product Name: Vostro1510
BIOS Version: A10
Vendor:       Dell Inc.
Is Dell:      1

and...
damien@vostro:~$ uname -srvmo
Linux 2.6.27-7-generic #1 SMP Tue Nov 4 19:33:20 UTC 2008 i686 GNU/Linux