I solved the problem by deleting both bluetooth preference files and rebooting. I was then able to pair my bluetooth mice. I have no idea whether this will work, but it's easy to try. There's one preference file in Home Folder/Library/Preferences. There's another one in BootVolume/Library/Preferences.
Hmm.