Quick snippet. I had a lappy that was had a wireless keyboard paired to it. I then tried connecting the keyboard to a different one, but no dice.
I then tried 'disconnecting' the keyboard from computer #1, but still nothing. Computer #2 couldn't see it, and when it could, couldn't connect to it.
I actually had to go the Bluetooth Preferences on Computer #1, connect the keyboard, and then delete/forget it all-together. After this, computer #2 could see it without an issue.
Resolved.