My MacBook Pro not working with batteries anymore?

Last month, my Macbook started shutting down intermittently, without a low-battery warning (at different times: around 21%, 60%, etc). I clicked on the icon at top and it said "replace now", so I figured it was time for a new battery (I was still using the original Apple one).

I ordered a brand new battery, which arrived yesterday. Charged it, and it worked fine on the first charge. As it started to get low (around 10%), it forced the computer into sleep, I had more work to do, so plugged in the adapter and kept working for another hour or so. I was getting ready to take it to another room (it was showing about a 60% charge by then). As soon as I unplugged the magsafe cable, the mac immediately lost all power (as before).

I let the new battery charge overnight again. Although it's registering 100% charge (and CoconutBattery is registering 100% charge and capacity, with only 3 cycles), the battery icon at the top is once again telling me to "replace."

This seems like it must be a hardware issue with my Mac, not the battery. Any idea what I should do to fix it? This macbook is too old to be covered under warranty. I'm farily confident about fixing things myself (unless soldering is involved).