Arduino external power source causes timing issues
From the description of your problem, it sounds like the servo is causing a lot of problems with the regulation of the supply to the micro.

What I think is happening is that the servo when moving is causing either a lot of ripple/electrical noise on the supply to the micro or tripping the current limit on your regulator causing the supply to drop out (if only for microseconds - which would not be visible on a multimeter - you would need a oscilloscope to see this) - either of these can cause the micro to be very unpredictable.

I would suggest using 4 AA batteries to power the servo, and a separate supply to the micro to prove this (you only need a common ground or negative for it to work)

Just a simple question what are you using for your 5v supply - what is it's maximum current ? - servos can take a very high current (over 0.2 amps to 2-3 amps depending on rating of servo and how much effort it need to move)