I had the same issue, just went on bluetooth, then clicking 3 dot and Advanced option. Turned dual audio On. Upaired the device from car and deleted from Both sides. Paired device again and its working. If it doesn't work, try not to allow contacts access for the first time.
It worked for me you can try it too.
Best of Luck
Mine is doing the same but worse now. Now I can't even connect to bluetooth at all. At first I could connect to call audio and not media audio now neither working. I am extremely upset about this. I paid over $1000 for a device that's not up to par with quality. If this isn't fixed asap I am returning it and getting the Iphone Xs!!
If you've tried every setting and cant figure it out try pairing to another deck and then go back to your original to see if it works. Worked for me and even contacted Samsung who has known about the problem, but dont have a fix for it. When I called them back to explain what I found out they asked for step by step of what I did so they could send it to their tech team. I made this video, but I didnt realize I was slow to the point lol. My first sentence in this comment in a nut shell is the video. If you have questions leave a comment on YouTube and I'll try to help you. https://youtu.be/ssClipSrdOA
Same bug here, Note 9 when connected once in your life with AKG Bluetooth Headset and car Bluetooth. The Bluetooth headset won't produce any audio output.
Tried all clear cache and data suggestions, but no luck.
Finally it helped to clear the cache and data from the "carmodeStub" system app.