I realize this is an older thread, but since I found it looking for help, I'll assume others will as well. My issue ended up being REALLY stupid, which is why I'm sharing it.
I recently purchased the newer Apple TV (4th gen) and had paired my older, but still working, Apple Bluetooth keyboard with the Apple TV to aid in typing in all the passwords I needed. Once I was done, I'm almost certain that I disconnected the keyboard from the TV and re-paired it with my Mac. As a matter of fact, weeks have passed without any issue... the keyboard was paired with my Mac and I merrily worked away.
Last night, a circuit breaker popped and my Mac lost power in the process. It was late at night so I didn't bother powering it back up. I just flipped the circuit breaker and went to bed. This morning, I powered up the Mac, but could not type in my password. Weird. I changed batteries on the keyboard. Still no joy. I connected a USB keyboard and logged into my Mac. I made several attempts to connect to the keyboard through Bluetooth settings, deleting bluetooth.plist, and rebooting, but nothing worked. My Mac could see the keyboard, and attempted to pair with it, but the handshake would never complete.
Then I wandered into my living room and noticed my TV was on. I had not turned it on. The new Apple TV will automatically turn on the TV if it receives any input (which is really cool), but the remote was sitting on a shelf untouched. Then it hit me. The keyboard, after losing connection to the Mac, had set itself as available and the Apple TV happily grabbed a hold of it. I confirmed my suspicion by going into the Settings page on the Apple TV and there it was... Apple Keyboard = Connected.
I re-disconnected the keyboard from the Apple TV, went back to my computer, and immediately made a successful pairing attempted. It's a weird story, and probably not one that a lot of people will experience, but the bottom line is to make sure your keyboard is not paired with something else.