Solucionado. Ya funciona Android Auto otra vez.
Por si le pasa alguien más. El error viene dado cuando tenemos una aplicación dual que hace uso de los servicios de Google. Una vez eliminada la duplicidad de esa aplicación y de los Google Services vuelve a funcionar con normalidad.