Step C0 C1 C2 C3
1 1 0 0 0
2 0 1 0 0
3 0 0 1 0
4 0 0 0 1
This is called "wave" drive and only one coil is activated at once. The stepper library activates two coils at once and in this mode the motor consumes twice the current and will have roughly twice the torque. Your motor will work with the stepper library provided that you get the windings wired correctly AND the power supply can handle twice the current. If the latter is true, then simply swap pairs of motor wires (with the power off each time) until the motor works.
Warning: disconnecting a motor wire while it is powered is a fairly certain way to destroy a motor driver.
For everything you ever wanted to know about stepper motors, see http://homepage.cs.uiowa.edu/~jones/step/