Stepper motor is heating up?
What kind of steppr driver are you using?  Setting the current limit with the power supply is a bad idea - it's not designed to do that, unless you are using a lab supply!  It would be a beter idea to invest in a proper chopper driver that uses a PWM drive on top of the actual stepping to set the current through the coils, and then use a properly-sized power supply.  There should be a way to set the drive current with either a software seting or a trimmer pot.  At any rate, the motor torque is determined by the coil current, and you will need to turn it up until it doesn't skip steps.  At high currents you may also need to cool the motor.  The drive transistors will certainly need a good heatsink, but they should disspate less heat than the motor.  

Edit: Chris remided me of another very important advantage of chopper controllers: driving the inductive motor windings.  Inductive coils will try to resist changes in current flow.  As a result, when the motor steps, the coil current takes some time to 'ramp up'.  If you want to step very quickly, you need to use a high drive voltage to so that the coil currents will ramp up faster.  This means that you need to use regulators on each coil.  Chopper controllers do this for you, and all you need to do is set the desired max coil current.  Chopper controllers can generally also microstep the motors, interpolating the coil currents to hold the rotor between steps.  If you use the proper controllers, then you can get away with cranking the supply voltage up to 24 or even 36 volts for better performance.