Chosen Solution
I had received a replacement #616-0435 for the #616-0431 to fix Error 29. Now the phone would only hold about a 10 minute charge, I would re-charge it and it showed 100% charge, but would never last more than 10 minutes. I may have gotten a bad battery replacement.
The problem turned out to be on the new battery. The electronics on the battery were shorting out, when the phone cover is pressed together. I cut out a small piece of thin PTFE gasket and inserted it in between the battery electronics. This seemed to have fixed the problem.
Petereyes, It sounds like you answered your own question. Get the vendor to replace your battery. Be sure you get OEM parts when making repairs for Apple products to avoid most of those types of problems.
petereyes, what iOS are your running. Some discussion about draining caused by firmware issues as well as bad sim cards are still ongoing. Your phone jailbroken? http://www.macnn.com/articles/09/09/21/f… I would also try to restore the phone http://cellphones.about.com/od/howtoguid… shows you how. See if that helps before you send the battery back. Good Luck