Before finding this discussion thread last Sunday, I had purchased a 27" iMac, took it home, did the intial setup, shutdown and cold-booted the unit and experienced the exact issues (and more) as described in this thread. On re-boots, the problem do not arise, but being new to Apple computers I followed both the manual, and the in-store instruction, which tells users to power-on the KBM before the iMac.
Well, after the first unit experienced this problem, I took it back and swapped out for a second unit. I setup the second unit in the store with two employees watching me and got the same results. The store employees were stunned, and no solutions, and I did a return for full refund.
Then last Sunday I found this thread and today went back and purchased a third unit, but it turned out it was on Snow Leopard and the issues did not exist. Unforutnately, while trying to do a setup in the store SL refused to update. Enter the store manager, swap unit for iMac #4 which wa on Lion, explained the past issues I've experienced AND this thread, and demonstrated.
Even though I disabled the Bluetooth Discoverable option, if I powered the KBM before the iMac I would have the problem in its full glory. On the other hand, if I did noting and waited until the login screen appeared, the KBM and Magic Mouse were already working and all was good in the forest. I took iMac #4 home.