Ok so I know I'm new here, however, I was having the same issue I have a Nexus 6P on N and a 6P on O the one on N would connect to the car just fine the one on O wouldnt. I uninstalled the version of andriod auto for O and manually instald the version for N (N ver. 2.3.716604 v O ver...