Appears that calibrating the battery was not enough. Went into the Apple Store, saw an "Apple Genius" and he instantly replaced it. No questions asked. A "new revision" apparently.

Let’s hope this fixes it!