It was definitely possible to downgrade to 3.1.3 a few days ago, did it myself when my first attempt at 4.0GM didn't work out.

These were the steps I followed to do it:

http://www.blogsdna.com/9175/how-to-downgrade-iphone-3g-4-0-os-to-3-1-3-firmware-on-windows-mac.htm
_________________________
Remind me to change my signature to something more interesting someday