[rainfreak]

I had the same problem last year with my wife's Edge and her iPhone. I removed the Bluetooth connection profile from Sync and then tried to pair again, with no luck. I also checked the iPhone and it was up to date on software updates. I finally plugged her iPhone into her PC, did a local backup of the phone, and then reset it to default (Settings/General/Reset/Erase All Content and Settings). After the reset I plugged her iPhone back into her PC and performed a restore, so that she didn't lose her apps, games, email settings, etc. When I tried it in the Edge that evening, it paired with Sync immediately and hasn't had a problem since.

Also, Ford just sent out an update last month for Sync. Did you get it in the mail? Have you already applied the update? I did and after the update not only is Sync much easier to use, but it pairs with our iPhones much faster and more consistently.