I putting power to the red/black wires coming out of the servo.
This would not make the servos turn. This will power up the servos, but they don't turn until they're given a "signal" on the yellow or white wire.
I am using HS-311's I didn't have a microcontroller to center them, I did what I thought was good by hand.
This definitely sounds like your problem right here. Without a microcontroller to center the servos, you have no idea whether your pot was centered or not. Now that you have a microcontroller, open up your servos and do the modification process again.
I unplugged the battery and one servo exhibited the behavior described.
Wait... the servo was holding without being plugged into a battery? Or do you mean it was holding when the battery was connected and then released when it was removed?
does the battery need to be unplugged when removing the programming dongle?
Yes. This is from step4 of the $50 bot tutorial:
Plug in your AVR STK Serial Port Dongle Programmer to both your computer and your robot if it isn't already from Step 3C. AFTER plugging your robot in, turn on the microcontroller by flipping the ON/OFF switch, or plugging in the battery if it doesn't have one. If you were to unplug the programmer, make sure you turn off your robot first.
Finally, try uploading the .hex file attached to this post. What its supposed to do is go straight, turn left, go straight, turn right, and repeat.