Allright I did this to get my bluetooth mouse working on my Dell Inspiron 700m:
I downloaded from synaptic these: bluez-bcm203x, bluez-hcidump, bluez-pcmia-support, bluez-pin, bluez-utils, gnome-bluetooth, libbluetooth1, libbtctI1, libgnomebt0, python2.4-libbtctI
Some of those could be an overkill though! (I am assuming as you said Ubuntu not Kubuntu you are using gnome)
Then I did this: firstly in terminal I typed
sudo modprobe hidp
sudo hidd --server --search
when it says "Connecting to AA:BB:CC
D:EE:FF" the mouse should run then.
I am still trying to get mine to run on startup but I made a custom launcher for my panel using "sudo hidd --server --search" to connect with the press of one button!
It worked for me so I hope that helps.