I've had a ticket opened on the issue since Saturday. I got a call back from Apple today and the support tech referenced a new document on the issue that was just released today. I've called him to get the link.
Anyway, the bug problem with bluetooth is how 'connected' all apple devices are via bluetooth, wifi, phone call handoff from iphones to ipads via wifi, etc, when using the same iCloud account.
The fix for now is to disable 'find my iphone', reenable it, and then restart the device. Since my iphone was already paired, doing this actually solved the problem - and it still works after a reboot of the phone.
If you can't get the device paired at all, even after the above, then reset your network connections. Then attempt to pair again after blowing away the bluetooth profiles on your phone and car(s).
I'll post a link to the document, but if you don't have multiple devices using the same iCloud account, you shouldn't be having the problem.
I'm sure there is a lot more to it, and this might not work for everyone, and quite confident they'll come out with a IOS patch to fix the problem, although the patch released today does not address the bluetooth issues.