I have a Nexus 5X with 6.0 Marshmallow and no problems using Android Auto. Maybe try clearing the app data for Android Auto in your phone?
Can you go back a firmware build and see if that works? It might even be helpful to look up what issues might already be common with the build of firmware you upgraded to on your phone.Yet, same here. I just spent an hour and a half resetting everything on the phone and the car's infotainment system, including a factory reset, twice. Nothing works. The Infotainment unit doesn't even recognise Android Auto on my phone anymore since I upgraded my Galaxy S6. It was working perfectly before the upgrade.