Comment 90 for bug 343727

Just for anyone here who still has this issue like me, I noticed
something interesting recently:

Due to another very severe bug (Bug 330824), I switched to kernel
2.6.30 (2.6.30-020630-generic). And sometimes the mouse starts
working, especially after the system is (re)booted or resumed from
sleep state. Although it may not able to re-establish the connection
after idle for a while, a simple reset of the bluetooth device
(hciconfig hci0 up/down) can let the mouse be discovered again.

To be sure, I also booted to kernel 2.6.28-15 and the mouse won't work
at all in any case, just like before. However, I noticed the dmesg
output at 2.6.28 and at 2.6.30 look similar to each other, both
saying something like:

[ 99.821915] input: Microsoft Bluetooth Notebook Mouse 5000 as /devices/pci0000:00/0000:00:1d.2/usb4/4-1/4-1:1.0/bluetooth/hci0/hci0:6/input12
[ 99.822127] generic-bluetooth 0005:045E:0700.0004: input,hidraw3: BLUETOOTH HID v1.00 Mouse [Microsoft Bluetooth Notebook Mouse 5000] on 00:0E:9B:DC:B8:0A

So, I guess this echos what Mihai Olimpiu Cristian has said above:
this might be a kernel related problem and not a bug with the
bluetooth stack.