Проблема известная, но возникала не у всех, что странно. Репортов написано куча и отзывов тоже, полно сообщений на форумах, редитах и техподдержки самсунга, но нигде нет решения. Как костыль есть вариант - полностью удалять АА с телефона и установить обновления заново, в результате чего, в 75% случаев подключение устанавливалось успешно. Но хотелось бы соединения в 100% случаев. И тут я заметил одну небольшую деталь, что во время переустановки АА, телефон почему-то запрашивает пинкод к папке knox. Это такая программа, которая клонирует приложения и создаёт безопасную шифрованную папку на самсунгах и некоторых других телефонах. И тут то я подумал, а не из-за него ли сбоит АА, т.к. машина то не в курсе, что могут быть клоны приложений в телефоне и подключается иногда не в тот Android Auto, а в клонированный, у которого нет никаких разрешений на подключения к автомобилю. После чего полез в гугл смотреть как удалить этот knox. Выяснил, что удалить его в принципе невозможно штатными средствами. Но однажды, ковыряясь в меню телефона, я наткнулся на настройки knox и кнопку удаления не его самого, а папки и всех приложений в нём. Тут то я с радостью удалил эту бесполезную, для меня, папку, и с полной уверенностью того, что теперь подключения будут стабильны пошёл спать. И вот прошло уже пару недель, как я удалил эту папку, ни одного сбоя подключения телефона к Android Auto не было. Так что пробуйте, может вам тоже это поможет.

Удалить папку knox в One UI 7 можно по пути - Настройки -> Безопасность и конфиденциальность -> Другие настройки безопасности -> Папка Knox -> Дополнительные настройки -> Удалить. Соглашаемся со всеми предупреждениями и жмём удалить.