I am using the Arduino NG to teach a class on embedded development under Linux and was having the same external power problem as has been stated. In fact all ten of the Arduino's in the class exhibited the same exact problem. So I decided to dig into the problem to solve it instead of just patching it with a resistor. Besides, the resistor prevented me from using that pin for what I needed.
Anyway, the fix is to replace the 1K resistor, R12, with a 10K resistor so that the ATmega168 (pin 3) won't back-feed power into the FT232 usb-to-serial chip (pin 5.) When allowed to back-feed power the FT232 would actually attempt to run which was causing a recurring spike on the RX pin every 35 milliseconds. That spike was enough to make the bootloader think that you were trying to download a program so it never got past the 10 second delay to start your program.
You can find R12 by locating the two LEDs, TX and RX, over by the crystal (silver metal can) then moving to the second resistor from the TX LED. That should be a 1K resistor. Remove and replace it with a 10K resistor.
Once I did that I checked to make sure that the USB pin of the PWR_SEL jumper no longer showed 3.5 volts when I had it jumpered for external power and plugged in. I can now program without any extra resistors or capacitors added to the board. All my sketches run normally on external power, too.
PS. If you don't have a 10K resistor you might be able to get by with anything from 6.8K to 12K but you'll have to test it to be sure.