Have you tried letting the battery run all the way down until the phone shuts off and then charging for several hours/overnight? That seems to be a common calibration procedure with Li-Ion batteries.
Apologies if that's what you meant by "charged it overnight" but I wasn't clear from the question on whether the battery was empty before you charged it. In any case a full discharge/recharge cycle might help.
Good luck!