The new battery, is it OEM or aftermarket? Sounds a lot like it is aftermarket. The $ you save buying one of those isn't worth it. If it is aftermarket I would suggest returning the battery and getting your money back so you can purchase an OEM one. This would likely resolve the problem.