I have the old, white, full-featured Apple wireless keyboard. You know, the one that actually gives your desktop computer all of the keys that you need
When I try to connect it to my iPhone, the iPhone finds it easily, but when I try to connect, I get the loading wheel. It eventually fails to connect. I've already unpaired it from the two Macs it was paired with and deleted the keyboard in the BT preferences on the Macs. This is an iPhone 4 running iOS 5.0. I had the same problem in iOS 4. The keyboard I am using is supported, according to Apple.
Here's the annoying part. If I press enter or return on the keyboard while the iPhone is "loading", a message flashes for about a second telling me to enter the 4-digit pairing key, but it disappears and says that it failed to connect because of a bad pairing key. There's no way I can enter the number in time, and I don't feel like trying to guess it.
It seems like the Apple engineer screwed up and gave it a 1-second timeout!!! 
But others have no problem syncing their keyboards.
I noticed that the keyboard still has the name I assigned it way back when. Maybe that has to do with it? There's nothing else setting my keyboard apart from the others. Is there a way to fully reset it? Taking the batteries out for a minute didn't do anything.