Hast Du es schon mal mit TomTom Amigo versucht?
Das hat einen deutlich reduzierten Leistungsumfang gegenüber der großen TT App, aber dafür funktioniert die über Android Auto ganz ordentlich.
Tutur
P.S.: es gab in den vergangenen Tagen diverse Updates für Android Auto - die hast Du alle installiert?