80 degrees Celsius is about the limit of what is normal.
Do you have a IR temperature meter. I bought one on Ebay for a few dollars and it turned out to be very handy to determine a hot spot on a board.
Perhaps when powering with USB, the voltage was too low for the Arduino.
Perhaps when using the external power supply, the voltage regulator got too hot and turned down the current.
Can you measure the 5V pin of the Arduino board ? It should be between 4.5V and 5.0V.