I've got a Mega and have been using it for a while via usb with no real problems. Now that I come to the end of my prototyping phase and I need to test it with external power, I got myself an 8v power supply (docs say 7-12v optimal input), it can supply 500ma (same as USB, but at a higher voltage, so more power).
When I connect it via the external psu, the output from the serial turns to garbage. I discovered by accident (plugging USB back in while powered up) that if I touch the outside of my usb connector (Connected to PC) to the casing of the usb socket on the mega board, then the serial output immediately turns normal. If I break the connection, it goes back to garbage.
So it looks like there's some problem with 0v from the external power supply, however, it produces a pretty good DC 0v-8v signal so I don't see why it's a problem.
Hmm. Ok so I tried the 12v line from a spare PC power supply (guaranteed high quality power) and a 0v line for the external supply an it works perfectly. Must be the cheapo wall wart I was using. Meh. It's an odd failure mode though, as I could see the program was running properly on the cpu as the LED was doing what I expected it to.
Your comment on "more power" from the wall-wart PSU is a little off. It is true that at 8v and 500mA the wall-wart is capable of "more power" than your usb connection. However since the first thing that happens on the Ardino board is voltage regulation, total usuable remains the same. (This means the board is actually dissappating more power since the extra 3V is dropped across the regulator.)
There is no such thing as "0V", just like like there is no such thing as "Ground." Both are references the rest of the world uses for "common." It does appear in your example there is an issue with Ground between your board and the Wall Wart. However, there isn't a problem with "0v".
It is very possible that the ground connection between your PC and your Arduino isn't very good, which is what is causing the garbage characters.