Stepper Motor Vibrating, Nothing Seems to Fix

I have access to a variable power supply during the week to see what kind of current draw I'm getting, but I'm using ordinary energizer batteries which should be able to supply up to 3A (although not for long, as they're typically only rated for ~3000mAh).

Appreciate the tip about adding a cap, I've got some coming in tomorrow that have a range of capacitances I can try.