Did you get back on to the store and seek resolution? If you're coming back in with the same serials they tried to fix earlier they will have a record of it.
> I brought it back to Apple after lots of phone calls and troubleshooting and Apple has now told me that something must have gotten messed up with the software. I am able to buy a new pair of AirPods if I would like to, or I can spend $250 for them to diagnose the issue (the price of a new set of AirPods).