Found this thread because of a similar problem. The last reply gave me the answer. I reasoned that if an external supply worked and the USB->Arduino cable didn't, then it might be because the battery voltage was lower and more appropriate. Sure enough, it turned out that I have a 3.3V display (not marked on the board, however), and I had been powering it off the Arduino's 5V supply. Doh!
I hope this helps someone else.