It is not possible to downgrade (or even restore to any non-latest firmware) on an iPhone/iPod newer than an iPod touch 2G/iPhone 3G. This is because on the 3GS and newer devices, Apple implemented a system where they must agree to and sign every firmware restore.
You can read more about it here: http://saurik.com/id/12
To get around it, you can save your "SHSH", which is the signature Apple gives you when they approve a restore. To do this, check out TinyUmbrella, but be warned that you can only save it for the latest firmware (iOS 4.2 at the time of writing, since that is all Apple will sign), and cannot use this to go backwards unless you already saved it for your target firmware.