I tracked down this thread after a couple of days of going back and trying to solve the issue. I was with Mark, where doing everything still had failed, but then I succeeded.
The most hopeful tip was the one above, about holding down the power button until you see the Connecting... message, but as written it didn't quite work out. Here's the steps that did work:
With Setup Bluetooth Device not open, press and hold the power button on the aluminum wireless keyboard, paying attention to the fact that the green light does come on (otherwise you're basically holding it in the off position!).
Select Setup Bluetooth Device from the Bluetooth menu icon. The keyboard is certain to be listed.
While still holding that button down, click Continue.
Don't let go when you see the Connecting message!
Soon after, the set of numbers for you to type should appear. Now you can let go of the power, and the sync up should work correctly.