I have a Microsoft Bluetooth Notebook Mouse 5000 and have experienced the same problem with two laptops, a Sony Vaio Z, and now a Lenovo Thinkpad T420s:
I can pair the bluetooth device to the computer, and it works fine until I either reboot, or put the laptop to sleep (either full hibernate, or just close the lid for a while).
In both cases the mouse will auto power off after a while. When I turn the mouse back on, though, the only way to use it again is to open the KDE Bluetooth device manager, remove the existing device, and re-detect and add it again.
I have 'trusted' the mouse in the bluetooth device manager.
I'm using Debian squeeze, with kernel 3.2.0 from backports.
My google searches have found many people with similar or identical problems, but no solution.