I have to also agree with your customer and would have refused the load. New tires (or any for that matter) have a horrible odor that could have infiltrated your product.
Food should travel with food, period. See below for specific examples
SQF
11.6.6.1 Vehicles (e.g. trucks/vans/containers) used for transporting food shall be inspected prior to loading to
ensure they are clean, in good repair, suitable for the purpose and free from odors or other conditions that may
impact negatively on the product.
CFIA
49. No edible meat product shall be transported to or from a registered establishment unless the transport container in which it is transported:
- (a) is constructed of material that is free of any noxious constituent;
- (b) has inside surfaces that are hard, smooth, impervious to moisture, in good repair and clean;
- © is capable of protecting meat products and containers thereof against contamination;
- (d) is equipped, where applicable, to maintain meat products in a refrigerated or frozen state;
- (e) is equipped, where applicable, to prevent meat products from freezing where freezing could adversely affect them; and
- (f) is not being used and has not been used for the transport of animals, control products as defined in the Pest Control Products Act (2002, c. 28) or any other material or substance that might adulterate the meat product.
FDA sanitary transport rule
www.fda.gov/food/guidanceregulation/fsma/ucm383763.htm
www.fda.gov/downloads/Food/GuidanceRegulation/GuidanceDocumentsRegulatoryInformation/UCM584453.pdf