I had a few false starts, but I think the thing that actually resulted in success was forgetting the car in my bluetooth settings and pairing again using the car's bluetooth menu.
The things I actually did were to:
- delete the key in the car
- forget the car in the car security section of the app (click image of key card then forget car)
- forget the car in phone BT
- Reboot phone and car (hold thumb wheels until screen goes black)
- Put phone in BT search mode and use car BT menu to connect to phone (gives a pin you confirm on phone)
- Accept all permission requests about contacts and whatnot
- Add the key from the security section of the Tesla app
Again, I'm pretty sure the only thing I really had to do was forget the car in BT and re-pair.