Just went through the same thing with my 2015 Sonata after I did the Verizon upgrade to Marshmallow. I thought it was totally borked, but with a little patience, I got it working.
Here's what I did:
-- First, go into Android Auto's settings (on your phone) and "forget" your vehicle
-- Then, uninstall Android Auto from your device
-- Reboot, then re-install Android Auto
-- Go through all the new "permissions" screens and accept the settings
-- Plug your phone into your car, and wait a few seconds. After a minute or two, you should see a notification on the phone's main screen that Android Auto is running, even though it is not triggering on the car's screen. Click that notification to see if there are any other settings or permissions to accept.
-- With your phone still plugged in, go back to the home screen, and check the pull-down menu. Click on any notification about USB settings, and try toggling to a different setting. I apologize that I forget which setting I chose, but changing that seemed to be the ticket to making the car "see" Android Auto on the phone.
(In fact, you might try the last step first before uninstalling and reinstalling -- it may fix things without doing the other steps.)
Hope it helps!