In case this helps, my Android Auto went through an infuriating phase where it refused to connect, and my cars screen would continue to say exactly what yours said. For about two weeks I was incredibly frustrated, until I discovered that I just had to clean out my phones charging port with a toothpick and it immediately began working again. The dust and debris from repeated connection and disconnection had piled up and prevented certain data pins from connecting, but once removed, it worked like brand new. I now clean out my phone’s charging port every month and haven’t run into the issue again. I was relieved that the issue was this simple to fix, and hope yours is too.