I find it odd that nobody else appears to be experiencing issues (including us). We use Touchnet and Catalog and we haven't seen this. How big of an issue is this? Are you unable to accept any payments and is your system is effectively down right now?
Do you know when Touchnet made these changes or have any specifics regarding what they changed?
I would presume if Touchnet updated their XML code for security purposes, they would deploy it everywhere. If so, wouldn't other customers also be facing the same issue?
Since I can't find a bunch of irate Touchnet customers makes me suspicious that while the XML may have changed, it's probably the interaction with something else that's causing this issue. Perhaps something unique to your organization or in your Catalog deployment?
If Instructure wants to charge you $70K to fix something, it sounds like they understand what the issue is so I'd ask for a detailed explanation.
Of course for $70K, I think I'd look into Touchnet alternatives. They're certainly not the only payment processor. I'd also make sure they knew that we were considering making a change as a result of the issue.