Had lots of problems with my apple bluetooth keyboard and hope this solution helps someone.
Symptoms: Keyboard randomly loses connection and very difficult to reconnect it despite trying: rebooting, charging batteries, switching bluetooth off then on again, trashing Plists, resetting PRAM, resetting SMC and more...
This worked for me and is very simple - the key is holding the keyboard power button whilst setting up - if I let the button go after keyboard is found, it won't pair.
1) Switch off keyboard
2) Go to System Prefs > Keyboard > Set up Bluetooth Keyboard
3) After clicking "Set up Bluetooth keyboard", press and hold the power button on your keyboard
4) Keyboard should be found after a short while
5) Continue holding power button whilst also pressing "Next"
6) 7 digit code should appear shortly - type it in and away you go.
Prior to doing this, the keyboard would be either completely invisible to my iMac's bluetooth, or it would be found but not pair. Possible that the keyboard has a fault but this solution seems to have refreshed the whole connection and it is now performing reliably (fingers crossed...)
iMac, OS X Mountain Lion (10.8.5), 27" | 2.7 Core i5 | 12GB Ram