I have exactly the same issue. Whenever I replace the batteries in my magic mouse I have a few days of constant disconnections. At first it's very annoying and the mouse disconnects every 3 minutes or so. It reconnects automatically in about 15 seconds but it's a huge pain. After a couple of days the connection seems to smooth out and become very stable. My guess is that it is something to do with the actual BlueTooth radio and that the signal strength might actually be too high at first. One note is that I have a magic mouse that I use with an iMac and that never seems to have the trouble, but the mouse that I've used with my laptops has always had this problem even with a couple of different laptops. It might be the mouse, but it also could be that when I'm using my laptops the mouse is only a few inches from the computer, but on the desktop the mouse is probably 2 feet from the computer.
Seems like it's a radio issue to me.