It mostly works with my Note 5.
Since my Note Edge is basically a Note 4, it is quite possible that the Note 5 has solved the audio problem and the tech didn't know - which is actually my point. I was left to myself to solve this for six months. There was no informed help anywhere.
And - as is typical for this situation - Samsung cannot tell me why it is incompatible, which means I do not know if there will be any fixes for it. Is it a basic hardware issue? No idea, but I doubt it. Digital audio is not like analog audio, so it isn't as if there is a low quality VCA chip in the phone that doesn't have the power or fidelity to put out the signal.
I will be replacing my Samsung Note Edge, which is basically a Note 4. It's unlikely to be another Samsung product (this is my 2nd Note). After spending $1200 on a new nav/sound system for my car, I discovered this problem and no one, anywhere knew anything about the issue - not via Android, my provider, Kenwood or Samsung - until just now.
I find the entire Android Auto experience with its very limited ability to choose music (as a built in safety feature) far too limited. By contrast, I plugged in my girlfriend's iPhone, and Apple CarPlay came up instantly and offered me a much more pleasant experience - and with full audio. Granted, all those playing options may promote unsafe driving, but the AA experience gives you fewer options than you would have if you had a traditional CD player and AM/FM radio.
Panda, I am glad that you don't experience the audio issue, it is very, very frustrating. If I could modify the title of the post to reflect your experience, I would, but the quote I posted came directly from my Samsung Support chat window, and despite my prompts for more detail, Samsung tech support said no other info was available.