won't i lose all my contacts?
No, you shouldn't if you have backups. I agree with the recommendations. It's also the advice that the Apple website would probably give too.
So I'd plug your phone into iTunes. It should say "backing up <phone name>" at the top and should spend a while doing it. Then, when it's done, in iTunes, go to Edit -> Preferences -> Devices and you should see a list of backed up devices under "Device backups". Check that the date in the right column matches today on your computer - so then you know it successfully backed up.
Then do as everyone says and do a restore. When that's done, iTunes should say something like "I see that there's a new iPhone installed. Do you want to import settings from a backup or do you want to set it up as a new phone?" Choose import settings from a backup and then choose the name of the phone. It should restore everything - including all of you SMS messages, all of your calling history, everything. It doesn't restore music and video and apps though, so when you are done restoring the data from backup, you'll need to do another sync to put all the music and apps and everything back on.
The whole process takes a long while. Be patient. When it's done, everything should be just as it was... I've never seen anything that's not backed up.