HTC One: KitKat Bluetooth issue

So I have a T-Mobile HTC One which I just updated to Kit Kat. Since the update I am unable to use my cars controls to make bluetooth calls. Car is a 2011 Hyundai Sonata. Prior to the update bluetooth worked perfectly for both hands free calling and music playback. Now I can playback music just fine, but when I try and use my steering wheel controls to make a phone call it pops up "downloading contacts from phone" for several seconds, then nothing. I can initiate a call over bluetooth by actually touching the phone, and it works fine over car speaker system. I have tried renaming phone and pairing freshly, but it doesn't make a difference. Anyone else having similar issues or have a solution? Really frustrating when an update breaks a feature you have come to rely on. Thanks in advance

OK so I'm replying to my own thread because I solved my issue and wanted to pass along what I did.
I spent hours trying to get this issue fixed, and after posting this thread decided to give it one more go while awaiting responses.
What finally worked was changing the language on the car bluetooth/voice system. According to the cars owners manual, yes I should have read it more closely hours ago, changing the language completely resets the bluetooth and voice recognition system for the car. After cycling through French, Spanish, then finally back to English I was able to pair the phone and car again. This time when I initiated voice controls from the steering wheel I got the "downloading phonebook from phone" message, and it then gave me the transfer was successful message and everything is working perfectly. I would never have thought that I would need to "reset" the car system, I made the assumption that deleting the pairing/devices and renaming both phone and car would have had the same result, but apparently not. You know what they say about assumptions!

tl;dr Instead of deleting pairing/devices and renaming, reset car bluetooth/voice recognition by changing languages, and then was able to successfully pair and load phonebook. Good luck!

Worked PERFECTLY for me on my Hyundai Elantra 2012

Thank you!

I had an issue with my HTC One pairing with bluetooth to my Ford 2010 Escape Sync system. The problem was different - it was not playing Pandora music through bluetooth no matter what. I read in several threads that people have solved BT problems just by deleting the device from the car's system, then reconnecting. I did that, and it actually worked.