Legally, some state consumer protection laws may come into play here - depending on your state; see State Consumer Protection Offices | USAGov - and there may be formal grievance processes after you fill out a complaint. And, nationally, there is the Better Business Bureau.
But for any complaint, you will have to present evidence or a strong case that you did not get the work done at the first shop and that your coupon wasn't fulfilled by them. It appears that it's a "he said, she said" situation with the local owner of the first shop. Unless the second shop would be willing to help and perhaps say that it appeared that no recent work was done to your vehicle.
You could take the first shop to Small Claims Court - State Listing in your county, but again, you will need evidence, and have to pay the filing fee and any other fees and schedule a court date. These may far outpace what you paid for the auto service itself.
Your best bet may be to contact the repair shops chain's national office. Any national retail chain will have an office to deal with complaints, and most will try hard to make good on bad situations, as their national reputation depends on having good customer relations. The national office may have limited oversight on the local shop, though. But the national office may make good on a valid coupon for the work as an ethical gesture.