I recently tried to upgrade my iPhone 3Gs to iPhone OS4.0 using windows and things didn't go according to play.

Here's what happened and how i fixed it.

1. iTunes updated itself.
2. iTunes Backed up iPhone
3. iTunes attempted to upgrade phone.
4. iTunes hung half way through install
5. I rebooted and restarted iTunes and the install completed.
6. iTunes attempted to restore the old backup.
Result: all my data was gone. (texts, emails, notes, photos)... very disappointed.

Next:
I repeated the process.... and tried to reinstall an old backup....

Result:
No luck, turns out the new iTunes update deleted all my old backups ... not happy

How i fixed my phone:
Luckily I use Windows 7 and used the Previous Versions functionality to retrieve old backups.

1. I located the backup folder (usually C:\Documents and Settings\USERNAME\Application Data\Apple Computer\MobileSync\Backup)
2. Right click the backup folder, goto properties>Previous Versions
3. Hopefully you'll see a old version of the backup from a time before you started the process (it should be a large file, mine was 185MB).
4. Copy this file into the Backup folder.
5. Open iTunes and attempt to Restore the backup.

Result:
My phone was updated to OS4 and all my contacts,photos,texts and notes were restored :)