while tuning an engine, yes, you can damage coatings, but remember, this is Stu's numbers matching original motor that's been in the car since the day it left the factory, and has already been previously tuned, by what sounds like, a wideband O2 sensor, so there's pretty much zero chance that his tune caused the coating to fail, unless he changed something else in/on the engine while the headers were off.

I'd be taking the headers TO the guy to show him how they failed--If all this was done over the phone, then he doesn't know what the failure looks like, but does know that off tune ups will damage the coating. If he continues to sing the same song about it being your fault because your tune is off, after he sees the headers in person, then cancel payment on your card, usually you have at least 90 days to do this, sometimes more if you get persuasive with the card company. If you paid by check/cash, then let him know you'll be letting everyone in the mid-pen area know how poor his quality of work is, and how lousy his customer service is after the fact.