As a quick followup to my own situation. I did follow through with a factory reset of my car receiver, then proceeded to only connect my phone as A2DP, to no avail. The automatic connection still seems restricted to only HFP. I have to echo the rest of my forum-mates here, that there is some bug with this device and whether it is Samsung or Android's misdoing I'm not sure.
I too, went ahead and re-installed the same app I recommended earlier on... better than nothing, although it would be nice if it completely automated the A2DP connection process instead of requiring a user-enacted trigger (screen unlock or power connection). I did write a review to the app page, suggesting this full automation.
Officially, is there not an option we can take to contact customer service or to notify the responsible party of just such a bug?