Yeah, this is a mystery issue. I've been able to Google this and found others like us. I use the Ford Sync system in two cars; both worked flawlessly until the update. Now, I can not pair the iphone to the Syncs. I get as far as the devices discovering each other and inputting the 6 digit code from sync, but then it still says no devices connected. My iPhone thinks its connected (blue tooth icon lit), but the Sync system is not displaying its icon. Worse, duting a call I can heat the caller, but my outgoing audio vanishes between the iphone and Sync; they can hear nothing. Even though Sync says there are no paired phones, the blue tooth audio streaming works fine.
I have not been able to connect my "backup" Motorola blue tooth headsets since the update either.