I have almost the exact same issue... But mine didn't start suddenly - I have never been able to get Android Auto to work. I gave up on it ages ago and kept using my stand alone GPS unit - but that has just died so I'm back here trying again.
I have a Pixel 9 currently running GrapheneOS 16.
USB-C is set to "On" Does not add any restrictions
USB Controlled by "This Device"
Use USB for "File Transfer"
I have tested this in two different cars - both (in their own way) report that there is no USB connection from the phone. But at the same time, the phone reports that Android Auto is connected to the car.
While "connected" I tried to change the setting to USB Controlled by "Connected Device" - but the setting change failed and the phone reverted to This Device.
In both vehicles, a standard Android phone connected with the same cable worked perfectly.
Clearly there is a USB connection issue somewhere - what am I missing?