I've had major performance issues on my iPhone 3G (which is over 2 years old) after upgrading to the new iOS 4.0. Apps took much longer to launch, password entry forms did not respond quickly enough and the whole experience was just much much worse than using the 3.1.3 firmware version. Unfortunately I quickly found out that Apple does not like you to downgrade the OS and firmware for reasons that are only known to them, regardless of the fact that the new OS clearly does not perform well on a 3G model.
I tried the 'normal' downgrade process using iTunes 9.2, a 3.1.3 firmware file which I downloaded from this site and entering the phone into DFU mode as described in various guides. However at the end of the restore process I always got Error 1015 which basically translates to 'Nice try my boy'.

Fortunately after unsuccessfully trying a few different approaches I came across this guide which uses the iRecovery tool after Error 1015 has manifested itself and this worked a treat. I managed to downgrade to 3.1.3 without issues following the steps described. So if you too are stuck at Error 1015 then give that guide a try - but you do so at your own risk of course.

Hope this helps someone.