No, it really is Malfunction. Battery Icon is black rectangle with white rim and red "Malfunction" in the middle.
I've tried to recondition the battery as you described. Didn't help.
Think I'll have to send this new battery to distributor. Maybe he can reprogramm it. At least give it new S/N and maybe change date of manufacture from "18 Sep 00" to something else..