As an update, this is what I did to try and solve the problem. It might have been the last step, or a combination of all of them.
1. Did a phone restart (didn't work).
2. Connected the car to my home wifi. Coincidentally, a map update was available, so I installed that (didn't work).
3. Connected my wife's phone (which has 12.2 installed) to the car. That connected just fine.
4. Tried my phone again (didn't work).
5. Told the car and the phone to forget each other, and then reconnected. Worked!