It's not Apple's fault, at least I don't think so. I've been using Win 7 since the first beta, and while I think it may be the best thing the M$ idgits have come up with yet, the bluetooth support has been pretty crappy. Sometimes a device will connect easily on the first try, but usually I've had to spend a lot of time dinking around with it before it takes. This has been the case with a wide range of devices and computers (I repair comps for a living). Three days ago I tested out my sister's Magic Mouse on my MBP and it connected immediately to both OSX and Win7 (haven't tried Ubuntu yet).
Yesterday I bought one. Worked great with 10.6.2, Win 7 just says "connecting" for-freakin'-ever, which is how I came to this thread. In the midst of the annoying forum-registration ritual, I got it working. I think what did it was turning the mouse on first, then adding the device (or maybe the other way around- I've already forgotten).
So all is well now, just waiting for a Windows version of Magic Prefs!