I had to unpair my Motorola bluetooth from my Droid before I could pair it with Apple. I had the Droid turned off so I figured my bluetooth would pair automatically with the iPhone. Once I unpaired my Motorola, the iPhone accepted it.
My Motorola bluetooth model is the elite flip. It does not work well with the iPhone. Several people complain that they hear an echo. Since it isn't that old, I exchanged it. The new one doesn't work that well, either.