This shouldn't be normal, My iPhone 3G (Which is just a gizmo that I have laying around, since I don't have AT&T, and am a die-hard Android user) is beyond jailbroken. It also has a custom bootrom, which allows dualbooting iDroid (iPhone Android/Linux Kernal) I've restored this iPhone many times, and it still works. If you want, you can put it into DFU mode, and restore 4.1 (Or 4.2 if it's out when you read this) and jailbreak with redsn0w (0.9.6b for 4.1, a 4.2-compatible version probably isn't available yet) this should fix your problem, If your still having problems, let me know.
*Note* if you install 4.1, it will update your baseband to the newest one (5.14.02?) if it isn't already. So if you use an unlock, then you'll have to wait for a new version of Ultrasn0w to be released for the 5.14 baseband.