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.