Transfering a Bluetooth keyboard & mouse from one iMac to an iMac that has never used Bluetooth
You'll also likely need to turn your keyboard off/back on and make it discoverable.

See:

http://support.apple.com/kb/ht1809

for a complete walk-through, but to be safe, turn off first mac, off keyboard, then back on while searching on the second Mac (using bluetooth control panel)

Alternately, instead of fully turning off the first Mac, you could just turn off its Bluetooth, which is much faster. But make sure you have a way to turn Bluetooth back on again—if you only have Bluetooth peripherals, this could be problematic.