On the phone with them, they said the card had been flagged as being used in fraud because we were off in the middle of nowhere, away from our normal spending patterns. The ONLY way to reactivate the card is for the CC company to SMS text us with a code, which we have to read back to them. The thing is, the very reason they flagged us - that we were way off in the middle of nowhere - also meant that we had no cell phone service, and couldn't receive the SMS. And given the vast size of Big Bend (getting out of the park from the hotel is a 45 minute drive), it was questionable if I'd be able to drive to a location with cell service if I couldn't fill my gas tank first.
The hotel manager overheard me arguing on the payphone with the credit card company, and he drew me a map of some pockets of cell service within the park, so in the end I was able to get it taken care of.
One ironic part of this was that the card is in my wife's name. When they wouldn't listen to her, she gave them verbal authorization to talk to me in her stead. They were willing to believe her identity for this, but not for the re-activation of the card, which doesn't make sense.
I also asked their CSR why they flagged the card. They said that I should always notify them if I'm going away. I asked them what the criteria is for that, since this was an in-state trip (I live in Austin, and Big Bend is also in Texas). The CSR said that's odd, and he doesn't know why that would happen.
So good for them that they watch for fraud, but the failure mode for their heuristic is the most catastrophic possible. If the very reason they flag me also prevents me from fixing the problem, then it's a rather badly-designed system.