Ref this link posted earlier.
http://forum.arduino.cc/index.php?topic=85335.0
First post mentions the stepper library is not suitable for this motor.
Also max speed 100 pps, so 500 rpm speed is far too high i think.
I would suggest try copying his code, get it working then modify.
This chap seems to have solved the problem
http://arduino-info.wikispaces.com/SmallSteppers
His symptoms would appear to be similar to yours , vibrting but not turning initially.
Also he has measured the stall current at 250 mA so a decent power supply is needed.
This chap
says 4.5v is too low so if your arduino is powered from USB lead , not good.
Sort out your power supply first or you could end up chasing your own tail with coding errors that do not exist.