1. Make sure you have the right version for your phone. There is a separate download for the iPhone 3G and 3GS.
2. Validate the checksum on the file you downloaded against my checksum. This will tell you if you have an official file or not:
ga-afrezell-20:~ dfrezell$ md5 ~/Downloads/iPhone2,1
3.1.3_7E18Restore.ipsw
MD5 (/Users/dfrezell/Downloads/iPhone2,1
3.1.3_7E18Restore.ipsw) = 4117e4b22565e69205a84e9eeef0583e
You will need to open up a Terminal shell and type the command:
md5 <path>/iPhone2,1
3.1.3_7E18Restore.ipsw
This takes a few seconds and the hex number should match mine: 4117e4b22565e69205a84e9eeef0583e
Here is the direct link I used to download the 3.1.3 version (iPhone 3GS version):
http://appldnld.apple.com.edgesuite.net/content.info.apple.com/iPhone/061-7472.2 0100202.8tugj/iPhone2,13.1.3_7E18Restore.ipsw
Apparently edgesuite.net handles a lot of companies downloads.
3. I tried earlier software versions and got the same error you did. This may be a "bad thing". From my readings of various posts, Apple validates software packages before installing them on the iphone. Unfortunately, they only keep the latests versions on the validation servers. So, when trying to revert back to a previous revision that is no longer available, you get the "could not be restored" message.
Another possibility is the phone needs to be in DFU mode when restoring from a failed 4.0 upgrade. This is different from Restore mode, in that the screen is blank (no plug or any graphics) but you still see the iphone in iTunes. To get into DFU mode:
a. Make sure the iPhone is connected to the computer via usb.
b. Hold the Power and Home button for 10 seconds (really, do the 1-one thousand, 2-one thousand count in your head).
c. After 10 seconds, let go of the power button but still hold the Home button.
d. Wait until the iPhone shows up in iTunes, then you can let go of the Home button.
e. Attempt the restore from file again (3.1.3 file).
Drew