Use some microstepping. Full steps lead to resonant miss-stepping (aka mid-band resonance), and is extremely noisy. Slower motion should allow some more torque, especially if not using full-steps.
You may simply have too low torque motors - if you are direct driving without reduction gearing this is more likely. Motor torque is strongly dependent on motor size if no gearing is used (which is why gearing is often used).