Which SparkFun stepper did you get?
My guess is your Easy Driver can supply enough current for the smaller one, but I think they can only sustain around 750 mA so I don't think it's enough for your bigger stepper.
Like the others say, for better performance you can step up the voltage. The Easy Driver will take care of the current.
The other thing I can recommend is using the AccelStepper library instead of just the immediate on/off of the Bildr example. It's easy to tweak speed and acceleration parameters until you get a good combination.
Good luck!