Same problem here on a Toshiba Satellite Pro S200.
Restarting the bluetooth service fixes it (sudo service bluetooth restart)
Ubuntu Natty fresh install. BT was working in 10.10
$ lsusb
Bus 006 Device 003: ID 0930:0508 Toshiba Corp. Integrated Bluetooth HCI
$ uname -r
2.6.38-8-generic
Same problem here on a Toshiba Satellite Pro S200.
Restarting the bluetooth service fixes it (sudo service bluetooth restart)
Ubuntu Natty fresh install. BT was working in 10.10
$ lsusb
Bus 006 Device 003: ID 0930:0508 Toshiba Corp. Integrated Bluetooth HCI
$ uname -r
2.6.38-8-generic