Yep, it really does work. Maybe not quite perfectly, but it's pretty nice that it works at all. Linux (in the past) has lagged behind new technologies, but it seems to be doing a good job at picking up new techs like this pretty quick.
I'm using both the Microsoft Bluetooth Desktop (1.0) and the Microsoft Bluetooth Desktop Elite 2.0 - so one is Bluetooth 1.0 and one is 2.0; both seem to work just fine. When the devices go to sleep, a keypress is all that's requried to wake them up.
The only thing that's not quite the best is that Bluez doesn't seem capable of setting up auth and encrypt per device; it's either enabled for all or none. So since the mouse doesn't request a pin, neither does the keyboard. I'm sure they'll take care of this in the future. I'm just glad my kde-bluetooth package works just fine :-).