iPhone 4S turns off before reaching 0%

I've changed my iPhone 4S battery with an iFixit battery last April.

Since then my phone keeps shutting off at 20% battery or above. (Most of the time between 25% and 35%)

I have checked the status of the battery with iBackupBot and everything is fine. I have restored the phone. Dis-charged it fully and recharged it fully multiple times. I have tried discharging it and plugging it back in for a few minutes and then let it discharge again.

I was hoping that the phone would "learn" about the new battery over time and that it would end up calibrating itself. But nothing has worked.

Is the iFixit battery a dud ?... Please help.