MBP Random Shutdown on Battery

Lately, my MBP has been experiencing a random shutdown issue. When my battery is around 60% full, the machine will suddenly turn off. If I try to turn it back on, it will only get to they grey screen startup stage before shutting down again. The only way to start up the computer is to either plug in the AC adapter or do a PRAM and PMU reset. However, even after the PRAM and PMU resets, the machine will shut itself down after a minute or two.

Has anyone else been experiencing the same issue?

I plan on taking the MBP to the Apple Store and hopefully they will just give me a new machine. I've already had the battery replaced twice, the HDD replaced, and the SuperDrive replaced.