Yep, I'm guessing they did some sort of update rather than just physically replace the battery. I should have done it myself. Best Buy is an authorized Apple service center. The nearest Apple store is quite a drive away. I haven't been motivated strongly enough yet. I expect there's nothing they can (will) do about it, too.
Oh, well.