Just an update.
I purchased an S6 specifically for Android Auto, but no luck. I had thought the issue was something to do with Samsung phones (as the Nexus 6 and HTC M9 had no issues connecting). I upgraded to the S6 from a Galaxy Note 3 (prior to lollipop update becoming available).
.
I installed the OTA update for Lollipop last night on the Note 3 just out of curiosity. I plugged it into the head unit (Pioneer 4100 NEX), and it installed almost instantly and everything worked perfectly including voice control (which I head the S5 was having issues with???). Anyway, just wanted to let everyone know that the OTA update on the Note 3 works perfectly, so the issue must not be touchwiz (as I left it intact just to test). I normally use Nova launcher and tested with it installed as well...it also works flawlessly. Maybe a simple S6 firmware issue? Go figure.
Note: There had been some speculation about what the cause of the S6 not working was. Here are a few thing that did NOT happen when I plugged the phone in, and a few things I observed.
1. Hands free or "car mode" did NOT activate when I plugged the phone in, nor did it activate at any time while the phone was connected.
2. There was no issue with Bluetooth connectivity. Voice works and all data from phone book was available. As for calling, full caller photo on screen along with phone controls you would expect (like dial pad option and mute)
3. Choice of launcher had no effect. I tried touchwiz, nova and Buzz. All worked just fine.
4. I tried 3 different cables. 2 standard white samsung cables and one aftermarket with the ferrite (sp) core attached to the end. All seemed to work exactly the same.
5. Phone continued to charge properly with all 3 cables. This testing took just over an hour and the phone did not heat up during this time.
6. There were no issues during connection or disconnection of the phone. I even tried unplugging it during active processes (like pulling up traffic, music and making a call). The head unit simply returned to it's normal screen almost instantly, and reconnected without issue when reconnected.
Let me know if you have any questions about what was done or observed.