All new iDevices (iPhone 3GS, iPhone 4, iPod 3G, and iPad) have to have special 'SHSH' signatures from Apple to allow them to install firmwares. If apple doesn't offer a SHSH signature for a version of a firmware, then you
cannot downgrade no matter what.
Older devices like your 2G iPod don't normally check for SHSH signatures from apple, so you can load pretty much any firmware you like onto them.
However, iOS4 introduced 'soft' SHSH checks for older devices, meaning that older devices that upgraded to 4.0 need a SHSH signature from Apple. Since you've already upgraded to 4.0, your device is now checking for SHSH signatures when you try to restore.
Since apple doesn't offer SHSH signatures for iOS3.x anymore, you're stuck on iOS4.
There is no way to downgrade.
You can back up your SHSH signatures using FirmwareUmbrella (Google it). You don't have to be jailbroken to use it. It creates a copy of your signatures for the iOS version apple is currently signing, which allows you to restore if or when you need too. You're too late to backup your signatures for 3.1.3, so you might as well backup signatures for 4.0 so you can restore to it if 4.1 is even worse.
Oh, BTW, I'm on a 2nd Gen iPod with iOS4, and my iPod is running perfectly. Maybe restoring and setting up as a new iPod rather than restoring from a backup will help?