I used to do this with my S4 (rooted and GPE ROM0 and had zero issues.
The Note 4 however (never rooted) is being incredibly unreliable. The audio streaming is sometimes ok but usually (90% of the time) it has a seemingly random number and length of disconnects. This manifests as a skip in the audio (It's still playing on the phone but not streaming to the head unit) and these can be short (a second or so) or long (5-6 seconds). Sometimes the audio never comes back.
I also have a fitbit force and it has a feature to display the incoming caller on the screen (through BT link to the phone)... This only works occasionally.
A quick Google search reveals dozens of reports of the audio skipping on BT streaming as well as a lot of posts about the Note 4 not conencting automatically while previous Samsung phones did.
The 0800 support line was _useless_ ("Have you tried turning BT off and on again, repairing devices? Well maybe you should do a factory restore then")
I did receive a call however from Samsung NZ from a genuinely helpful gent and he recommended booting the phone in safe mode which prevents any non factory apps from running to see if I could replicate the problem that way - I haven't had a chance to try that yet but wanted to see if I'm the only person in NZ with this issue.
The car stereo in question is a cheapo double DIN Chinese Nav unit and has worked perfectly with a Galaxy S3, S4, iPhone 5 and iPhone 6+.
Since the problem has occured, I have retested some other handsets with the head unit and they continue to function perfectly.
Anyone else? Suggestions? I promise to report back after trying the safe mode test tonight.
Cheers - N