Restoring Software error 29

Recently I replaced the battery in my Iphone 3gs. The old battery was an APN 616-0432. I replaced it with an APN 616-0435. I put my phone into DFU mode to restore it. Whenever I try to restore the software I receive an error. My question is does the replacement battery have to have the same part number in order to work? Or am I just running into a software issue.

Thanks,