I uploaded the "hello world" example to the Arduino Uno. As long as the board is connected to the USB port of the laptop, I see the message on the LCD. However, once I disconnect the board and plug it to the external power, the message disappears.
Why? didn't save the code on the chip?
Yea it did, that's the only way to run it. Probably a connection problem with the external power supply. schematics and (clear, not taken with a potato) pictures please 
OK.... funny...
The power supply voltage was less than 4V!!
The screen was on but showing the characters. Increasing the voltage to 9V fixed it.
I will delete the topic since it is crazy!
You put 5v into the barrel jack (or onto Vin).
This feeds the internall regulator, which has a 1.x volt dropout, so the voltage you wound up with was in the high 3.x range.
If feeding with external 5V, either use the USB connector (plugged into phone charger or battery power bank), or connect directly to 5V pin. If you connect external 5v to the 5v pin, do NOT use the barrel jack or USB connector with power connected in that way (that's why I recommend using the USB connector to get 5v in - it keeps you from plugging in USB while it's powered)