My laptop, a Compaq Presario V2000, has a built-in Bluetooth module that has worked well since at least Ubuntu 8.04 LTS. I use it to pair with headphones and a mouse. These both worked great in Ubuntu 10.10 (and still do with a live CD) but I cannot pair to any Bluetooth device in Ubuntu 11.04, even from a live CD.
I can see the Bluetooth module in lspci and when I try to set up a new device from the Bluetooth indicator my computer detects all Bluetooth devices around me but pairing always fails. At the moment I'm most concerned with getting my Microsoft Wireless Notebook Presenter Mouse 8000 paired.
Relevant output of lspci:
Bus 003 Device 002: ID 03f0:011d Hewlett-Packard Integrated Bluetooth Module