First off make sure you have the latest version of iTunes (8.01) Than:
1- If you can not restore for iTunes go to your phone settings// general// reset// erase all content and settings.. all information will be erased to it's orginal settings. This may take a few minutes.
2- Than plug your phone into iTunes.
3- iTunes will give you a choice of restoring the phone as new or from a back up.
4- Your choice. restoring as new will eliminate the chance that any software related problems that may have been backed up will be put on your phone again. However you will have to re-do any settings/email accounts/ apps etc. If you restore from a backup all settings and apps (and potential corrupt files) will be transfered to your phone)
PS: This advise is for locked and "Un" jail broken phones.
PS: By installing the latest version of iTunes you will also get the latest iPhone firmware version 2.1