I've got a iPhone 3G, never tried the other. It paired easier than any other phone, just following the info from the car. Turn the key on, without the engine running, and do the pairing. Then turn the key off. Wait 30 seconds or so, then turn the car on. That's the way I do it and the iPhone 3G has been working great. It might be different hardware/software from yours, I don't know. Good luck!