Legally, some state consumer protection laws may come into play here - depending on your state - 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 say that it appeared that no recent work was done to your vehicle.
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.