Have you measured the resistance of the motor coils?
The problem with using an L293 for a driver is that you have no method of limiting the current through the motor. If you use a proper stepper motor driver (see, for example the Pololu A4988) you can limit the current and drive it with a much higher voltage for better high speed performance.
...R