Make sure that first battery you tried is charged. I bet if you left it on there and twiddled (is that a word?) the servos some more, the problem would return.
My logic is that batteries, when drained, will "recover" slightly if you leave 'me be for a bit. Then, when you plug it in after it's rested, it works fine... for awhile.