It may be a bit different depending on model of phone:
Settings -> Application Manager -> Google Play Services (puzzle piece icon)
In that window, my display had the three vertical dots (menu) in the right corner. Clicking on that brought up "uninstall update". Click that. Once all of that was done, I restarted my phone, plugged it into the car, and it worked. Of course, now my phone has about 3 alerts telling me I have to update Google Play Services or the maps won't work. However, I tried that via the Android Auto, and it worked fine.
I hope this helps!!