Hi,
Where does your servo get it's power from? Please don't tell me it's the Arduino!! You never power servos or motors from the arduino it can't deliver the current these need. Servos are usually 4.5-6v, and are you using one of these tiny square battery's that still can't provide enough power!! use 4-6 x AA's mush better.
Power the arduino via the Vin pin (7v+) from the batteries, also to servo. Are the servo and arduino grounds connected?
Let us see your schematic or a drawing of it!! We need more info to help you.
Regards
Mel.