There are several threads about this, I had the same problem last year and also had to have Tesla reset the car’s fob programming. This seems to be one reason they do the fob battery replacement at the annual service because they have the car in the shop.
Last week I did replace the battery in one fob of my X and it worked. Here’s what I did different. I did it in a few seconds and within range of the car. I’m surmising that having the car awake and seeing the fob had it accept/re-acknowledge the fob when it came online. Before I did it in the house and it didn’t recognize it.
I’ve never heard of one dying killing both of them but anything is possible. I also thought that perhaps it has been made better with recent software but obviously not, so perhaps my process helped (short downtime, car active, etc.).
