Well you shouldn't run the servo from the Uno's 5v supply ever anyway: I wonder if this is a current related thing? (I assume the motor shield supplies the motors from an external supply, not through the Uno?)
First thing I'd try is to hook the servo to a 5v of its own, with that ground to the Uno's ground.... you never know, it might fix the problem, and it's the right thing to do anyhow 8)