Danny,
I'm not sure I can be of much help, but I'll try. Is that all they said -- was there any verbal or written explanation as to exactly what they mean by "certified product"? If I were in your shoes I would go back to the customer and ask them exactly what they want. Since there has already been one screw-up, you don't want another misunderstanding making you look worse.
If for some reason you cannot or don't want to ask, my interpretation (guess) would be that they want you or someone else in authority at your company to personally vouch for or "certify" that every shipment meets contract requirements. You can do that however you want (100% test, sampling, SPC, etc.) as long as you are satisfied that the shipment meets requirements and you are willing to put your name/reputation on the line, which means you are also putting your company's name on the line more than ever. Be careful, you don't want to blow this one. Use this as an opportunity to implement a good CA to solve the problem permanently if possible. JMO.
Does this help?