Depende mucho del teléfono y la versión de Android.
Primero hay que conectarlo con el cable (usa el de tu teléfono con el adaptador si es necesario). Que te conecte al Android auto de esa forma.
Luego desconecta y en la app de Android auto del móvil hay una opción de "inalámbrico" que debe estar marcada. Quita también el bluetooth.
Ahora vuelve a poner el bluetooth y la ubicación. Si todo va bien te debería conectar