Did you tie the grounds of the power supplies together? Also, you didn't mention the voltage/current ratings of the servo power supply; should be 6V and around 1 amp or greater for standard servos.
it's rated 4.8V - 6.0V(max) @ the manual.
yes, did tie both GND connection, motor -ve and Arduino -ve, so that they're common.
i've given up on my severino. i will purchase a new Arduino Mega @ www.myduino.com from i come from (cheapest in Malaysia)
and there's no stock for Duemilanove.