I have a serious problem with my iPhone 3Gs.

My phone was jailbroken to iOS 5.1.1 using Redsnow (tethered) and then it got stuck on DFU mode even after I jailbreak and restore it with an untethered version of snowbreeze. However, I was able to fix that problem - changed the battery, downgraded and all that. And then, I planned to restore it again using snowbreeze's custom ios 5.1.1 in iTunes. I didn't want to do it while in DFU mode 'coz I really hate it! But, when I tried to restore in iTunes while in normal mode, it went to recovery mode. That forced me to put it into DFU mode again. And then I restored... and it didn't reboot! I tried rebooting it using the Just Boot in redsnow and it worked. I found out that the tethered jailbreak of my iPhone is still there even if I already got it fixed beforehand. What's happening? Why's the redsnow tethered jailbreak still there even though I've already restored it to stock ios 4.1 and changed the battery?