I have not been able to downgrade 3.1 to 3.0.1 on a 3GS. I have tried with Mac and iTunes 9 and also on Windows 7 with iTunes 8.2. iRecovery will not find the Phone. The minute you try to load the new (old) ipsw, Apple verifies eligibility for the ipsw. Since the downgrade is not eligible (since 3.1), it removes the iPhone from the USB port. Re-connecting does not solve the problem.
I'd like to hear from anyone who has successfully downgraded a 3GS (not a 3G) and find out how they overcame the "iPhone/iPod not found" error n iRecovery.