I am going to assume you are on iOS 5.x.x, in which case, that would suck. Immensely. If not, then follow this nifty guide. Done it a few times myself.
Step 1: Back up your phone.
Step 2: Download TinyUmbrella. (
http://thefirmwareumbrella.blogspot.com/)
Step 3: Back up your SHSH blobs. (
http://lastplaceonthe.net/backup-shsh-blobs-tinyumbrella/)
Step 4: Use TinyUmbrella to bypass auth requestes from iTunes to apple.
Step 5: Restore your iPhone with the version of firmware you previously had on it.
Step 6: Move all your junk back onto iPhone from backup in step 1.
Read this:
Windows:
http://www.iclarified.com/entry/index.php?enid=16512
Mac:
http://www.iclarified.com/entry/index.php?enid=16496
It says its used for 4.3.3, but the process is basically the same for any version of iOS except iOS 5.x.x.