I had the same problem that others have mentioned about a sketch failing to run when the serial port is disconnected. When USB connected to the PC, it was fine. When power only it wasn't.
What worked was changing the USB cable. The failing prior cable was power-only. A couple of LEDs were blinking furiously with the failing cable, and never stopped. (Yun Rev2. The prior rev didn't have this issue)
After many other suggestions didn't pan out (or I implemented them incorrectly), my guess was that the USB data pins were floating. Many of the suggestions point to this kind of issue. I changed the USB cable to a fully fledged data cable. The LEDs blinked only occaisonally during startup, then stopped. The sketch came up as it should.
This is an easy thing to try should anyone else run into it.
Note that I wasn't using a wall charger, but an old printer box with USB ports. This would have connections for all of the pins, with none floating.