Shield seems to have an impact on the behavior, but a blank arduino with blink sketch will not start bootloader too (not often but it does)
You may want to measure the amount of current your shield is drawing. Sounds like on power up the power rails are unstable. If the shield is drawing too much current, the regulators would be having difficulty stabilizing. This would prevent the 8u2 and ATmega from properly coming out of reset.
It doesn't explain why it would happen when the shield isn't connected, except if one of the on-board regulators is now damaged.
As a alternative measure you may want to place a large cap on the RESET line. It may help to hold the ATmega in RESET a little bit longer, giving more time for the rails to stabilize.