For posterity, the solution:

First, I dug into the VW head unit menus. There's a "factory reset" menu with a bunch of choices. I reset the Bluetooth, the screen casting, and a few other things.

This was enough for my phone to work with Android Auto, over the USB cable. It wasn't enough to make the AA Wireless work.

The AA Wireless app troubleshooter walked me through some other steps, like deleting the Bluetooth pairing between the phone and car. None of this worked. So then I did a factory reset on the AA Wireless box, from within the app. This worked. After going through the setup process again, the phone and car now talk to each other.

Moral of the story: when things get weird, factory reset all the things.