Sounds like you are dropping pulses. Why?
Maybe you should give the circuits you are using, the code and a hardware description that includes the clock rate.
If you are using the Mega328 you can run it up to 16MHz -- is that the case?
As someone said -- ans oscilloscope is a marvelous thing. It can tell you the nature of the pulse ... nice and sharp or soft and squishy? There is too much information missing to be terribly helpful.