Hi Dennis,
I think by the frequencies you are measuring and the linearity of the error is clear evidence that speed is not the issue.
What isn't clear is what else is going on. You are a litle vague in that we have no idea what you are doing except measuring a frequency with an external interrupt.
So,
How are you implementing your solution?
What else is the processor doing?
Do you have timer interrupts going off periodically?
Assembly or C?
How are you converting to frequency?
Fill us in, we can help!
Allen