Stepper Motor Startup Time?
There is no startup time.  There is inertia in the rotor but for your application this is negligible.  I suspect there is an electrical or signal problem.  

Have you looked at the output signals to the motor with a scope or logic analyzer? You may not be outputting what you think you are.