Your speculation about tolerance interference between old and new gears may be valid.

I've had to fix three "electronic" odometers (rather than cable) over the years, and using OdometerGears.com as a source, have never had the problem you described, but I've always bought them as a set: the smaller gear plus the larger gear. For a few extra bucks, it's been worth the precaution -- I order the pairs before dismantling the odometer because I want to avoid the car's "down time" (waiting for the parts), so I don't know in advance which is broken. Once, the problem turned out to be the solder joints, but I also replaced the gears anyway.

My point, which I can finally get to :-), is that perhaps replacing both gears (from the same source) would eliminate the tolerance issue that you've observed. The real cost of the repair is the *time*, not the purchase of the gears, so isn't it worth the precaution to buy a pair of gears each time?