I agree with Runaway Pancake, but to be more specific, the Arduino 5v regulator can only supply 800ma (according to the datasheet). Many servos can pull 1.5A or more. You should also use a better 5v supply, as well as a fairly nice size capacitor on the power rails of the 5v supply (servos can be extremely noisy).
I'm curious though, how are you getting the 9v supply from the NXT? Did you wire directly into the battery compartment?