Just keep trying to update and restore through iTunes. It worked after the 4th time on my 3GS. If that doesn't work, go to an Apple store and get a new phone for free (if it's still under warranty) or call Apple and ask for advanced replacements. If both fail, save some money and get an iPhone 4. It's really easy to jailbreak, no issues as of now after jb/restore 5+ times <--- done it 5 times since I tried apps that weren't compatible with iOS 4.1 and stuff got messed up.
My 3GS crashed the whole time when it was jailbroken. iPhone 4 FTW