I'm a compete newbie at microprocessors but I do know a bit about stepper motors from building a CNC machine recently so here's my "dos centavos":
(I'm assuming you are using a stepper motor otherwise all of this is not true.) Steppers can easily lose steps. In other words the step pulses are generated but the motor doesn't move for a few steps. This usually happens when the load exceeds the torque of the motor. (and torque in a stepper drops off quickly at higher speeds). The same thing can happen if the motor accelerates too quickly. Using encoders and a PID loop to control steppers doesn't work well because the the motor will try to accelerate too fast lose steps and then compound it by accelerating even faster. So, usually a closed loop motor control uses a brushed motor or on larger machines an AC or brushless DC motor. It is possible to use the encoder count to compare to the steps and generate an error condition as a check however. I've considered using that method for my current project (unless I end up going with a closed loop servomotor setup)
Another thing to remember is if there is a load on the motor you need an acceleration ramp to avoid the problem of missed steps. If your going from 8k to 40k steps/sec in the space of 8000 steps you have a very high acceleration so I think that is why you lose the steps.
All of the above may be complete BS though
. I'm really just passing on what I've picked up from various CNC forums. You might want to check out http://CNCzone.com
where you'll find a wealth of info on motor control and can get more knowledgeable advice than mine.