I suspect you are powering the stepper motor from the arduino 5V shield pin, is that the case? If so, your symptom means that a small 9 volt battery simply can't supply enough current to operate the motor, but the USB current (it can supply up to 500ma) does have enough current capacity to operate your motor. Those small 9 volt batteries are almost useless for powering an arduino project in almost all cases and they are an expensive power source for the small amount of power they can deliver. Find a proper external power source for your board and you will be much better off.
Lefty