While the iOS 4 update brings a number of enhancements to the iPhone 3G as well as the iPhone 4, a few iPhone 3G owners have had enough problems that they want to restore the phones to their original states. There are ways to try resetting and restoring the new operating system to get it working, but sometimes the easiest solution is to downgrade.
Unfortunately Apple does not provide a supported way to downgrade its operating systems; however, with the iPhone 3G specifically there is a utility that enables this when coupled with the iTunes "Restore" function.
Here's how to do it:
Locate the previous system backup in /username/Library/iTunes/iPhone Software Updates/.
Download "RecBoot" from "http://www.sebby.net".
Connect phone to computer and press power to turn it off (use the slider).
When the device turns off, press both the power and Home button together (for about 10 seconds).
After 10 seconds, remove just the finger from the "Power" button (keep the "Home" button pressed--for another 10 seconds).
iTunes should detect the phone in "recovery" mode (click "Ok" when you see the message).
Select the phone in iTunes, and then hold the Option key while clicking the "Restore" button in iTunes.
Select the previous system file (found in step 1) and continue to restore the device.
An error will pop up that says you cannot restore to a previous OS. At this point, open "RecBoot" and it should dismiss the error and exit "Recovery Mode".
Sync your iPhone, which should now be running the last OS used (likely version 3.1.3).
Technically with this procedure you are restoring the old iPhone state, and are not really installing the old iOS version over the new iOS version, but the result should be the same. If you do not have a previous system backup in the "iPhone Software Updates" folder, grab the latest version of iOS 3 for the iPhone 3G at this Web site (it is specifically the one called "3.1.3 (3G): iPhone1,2_3.1.3_7E18_Restore.ipsw") and use that to restore your iPhone 3G.