There are several sources of error that are inherent to the methods used here. I'm going to talk about a few of them, and how I'm going to reduce or eliminate them.
The first is timebase error. There's not much that can be done to increase the initial accuracy of a crystal, but one can increase its long-term stability by making a ghetto OCXO -- an oven-controlled crystal oscillator. This is actually pretty easy -- and is what I'm planning on doing for the basic timebase. By creating a feedback system using a negative temperature coefficient thermistor, a transistor, and a couple of resistors, you can send current through another few resistors to warm up the crystal and hold it at a stable temperature. This reduces short and long-term drift, particularly if you always keep the OCXO powered.
Another source of error inherent to this design is flow-through error generated by the delay that it takes for the flops to flip in a chain through the counter stages. At lower frequencies this isn't significant, but it could add up to at least a few counts per reading at higher frequencies. This error can affect both the timer counters and the signal counters. However, with a higher-frequency timebase, one can do something like a cross between direct and reciprocal counting -- instead of assuming that the timebase counter has stopped where you want it, you read the overcount. A little math allows you to eliminate or at least significantly mitigate this error. This should work better the higher the frequency of your timebase, and worse the lower the frequency of your timebase. The basic 32KHz timebase will be useless for this kind of correction, because the time for ripple propagation is significantly less than 1/32678th of a second, the period of one cycle of the timebase.
The gate itself should be an insignificant source of error in the circuit; except at frequencies approaching 100 MHz, the MUX and gate operation should be much faster than the frequency being measured.
The Arduino itself is irrelevant to the inherent precision and accuracy of the circuit, the way it is designed. It doesn't matter how sloppy the timing of the code is; all the Arduino does is say "GO!" then wait for the rest of the circuit to say "Done!" before reading the data, doing the calculations, and resetting the circuit.
Finally, I'll include code to allow for calibration of the frequency counter from a reference source. This will basically just add or subtract a value to the timebase count before doing the rest of the frequency calculation.