iPhone stuck in Recovery Mode following battery replacement + restore

Hello!

I bought the iPhone 4s battery replacement kit, did the replacement, and afterwards had no service (stuck in "searching" but otherwise the phone was 100% fine). I went with the recommended fix of restoring my iPhone, but that's where things went bad. I'm currently stuck in recovery mode, unable to restore my phone due to some hardware error that stops the restoring process. I put the old battery back in - same problem. Cleaned anything metallic I had touched - no luck. Seems to be some hardware issue. The "four delicate prongs" mentioned in the guide are still intact and everything else is back in place (including the small black piece with a gold tip which popped out but I put back in). The ONE thing that does look a bit off is that on the left side of the battery (when looking into the opened-up phone) a little strip of silvery stuff seems to have come off from the left side of the phone's interior when I took it off, and is now on the battery - perhaps just adhesive? But the phone turned on and connected to wifi and worked perfectly after the replacement - the only issue was the "searching" thing. Now, only after trying to restore my phone, has this issue come up. Macbook and Itunes software are up to date, and they couldn't get it to restore in the Apple Store either.

Any suggestions would be much appreciated!

Thanks so much.