OK, so since the original post, I've upgraded to Windows 7 and Ubuntu 9.10, so let's see what's different.
Originally Posted by dgttm
In Windows, go to Bluetooth Settings (in the Start Menu, type in "bluetooth" and choose "Change Bluetooth settings"). There, go to the Hardware tab and select your primary Bluetooth radio (for me, one had a physical location and the other had the first one as its location, so I picked the first one). Hit the "Properties" button and go to the "Advanced" tab. Here, you'll want to copy down the Name and Address.
OK, now, on Ubuntu, go to the terminal and type the same command as before, although a sudo would probably help:
where "name" refers to the Name as stated in Windows (including the quotes). As I said before, you could also go into the Bluetooth Settings in Ubuntu (System > Preferences > Bluetooth) and change the "Friendly name" to match that in Windows.
sudo hciconfig hciX name "name"
I would assume you could change it the other way around (match Windows to match Ubuntu), but I think this is probably the easier route to take.
Now, I'm not sure if you got this far or not, but I had to cover my bases. If it's still not working at this point, you just have to make sure that the mouse is using the same PIN on each OS. When connecting the mouse, it should ask you for a PIN. You can have no PIN (not a big deal for a mouse), but you have to have no PIN on both. If it doesn't ask for a PIN, then I would assume it's using the default PIN for the mouse, which can probably be found on the underside of the mouse or in the documentation that came with it. If you still can't find it, Googling the specific model of mouse may help. You then need to try putting in the default PIN on the other OS for the PIN.
At this point, it should work, but if it's not, let me know (as a reply here, not another PM) with specifics.