My experience hasn't been exactly this, but i have had issues being stuck in a restore loop (error 29) after i swapped out an old battery for a new ifixit battery AND THEN tried to update to iOS4. (It worked fine while i was still using iPhone OS 3.)
Once i attempted the iOS4 update, my phone went into a restore loop never to come out. See my original post for more details:
Why do I receive error code 29 when I attempt a restore?
At this point, i'm going to (try to) purchase an original OEM battery and see if that will unbrick my phone.