Han sacado la nueva versión de Waze 4.58.0.1 y persiste el problema de la aplicación a través de Android Auto del coche. En cambio si lo desconecto y uso la aplicación desde el móvil directamente, funciona a la perfección.
Habrá que seguir esperando a la solución. He leído en algunos post en inglés que hay gente que lo ha solucionado, pero no me he enterado muy bien como.