I chimed in around page 8, or page 10 or so…wanted to check back in & say that a full Reset Settings (*not* just Reset Network Settings) DID work…but only temporarily.
As others have pointed out on this thread, once you unpair the iPhone with your car, erase all traces of the iPhone from your car, and then do a Reset All Settings on iPhone, yes…Bluetooth connectivity returns and works.
But only for a short time. A reboot of the iPhone, or a sync with a computer, and it's back to streaming audio of any kind just fine but NO PHONE CALL capability. At all. Either my car radio will disconnect from the iPhone (in my case, an iPhone 6 Plus) immediately and connect about a minute later but still not work with telephone functions in any way.
My car is a Toyota Prius C Two, 2013. The Gold Master of iOS 8 worked fine on my "old" iPhone 5, but once the public version of iOS 8 dropped & then I received an iPhone 6 Plus, it doesn't work at all. I can't find a Gold Master of iOS 8 for the 6 Plus (I'm in the Developer Program). Wish I could, I really want phone functions to work.