I think people (myself included!) have misinterpreted your post to mean that a test house failed you on compliance and provided a report saying so, not that they simply had trouble using your product with a Cat3 cable. I don't think it's really reasonable to expect a Cat3 cable to 'just work' with modern equipment, it won't meet spec for 100base-TX or better, and almost all Ethernet interfaces are 'or better' these days. So outside of curiosity, this seems like a don't care to me.
Does your product support 1000base-T (Gigabit Ethernet)? Pretty typical for a Cat3-era cable to only be two-pair, and if they were connecting it to 1000base-T equipment on both sides, a 1000mbps link will be negotiated, but fail to function at all with the missing pairs. It wouldn't meet the integrity requirements for > 10base-T anyway, even if it did link, so there would be no expectation of it working properly (though it likely would, at least for a short run), and most modern equipment is going to want to link up at 1000base-T.
If it's 100baseTX or 10baseT, it could be a crossover issue, depending on whether your/their side does AutoMDIX or not. Almost any PC these days will do it, but an old switch or whatnot that's been sitting in their equipment rack for 20 years they might be plugging it into may not.
You can mess up the PHY implementation, of course, but not really in a way where an improved cable spec would help (it mostly affects crosstalk and the like), at least that I can think of. This is typically all handled in the COTS PHY and you simply wire it to magnetics and the jack that are also purpose designed. I'd guess it's one of the above things (missing pairs, crossover, out-of-spec) or that the cable is simply bad.