Power seems very likely then. Page Parallax Continuous Rotation Servo - Parallax says quite a bit about power supply. What applies to Basic Stamps is similar for Arduinos. Try powering the servo separately with something like 4 x AA batteries, preferably rechargeable.
Steve