Maybe the reason why you cant downgrade from new boot is because your phone came out with the new boot?
My 3gs is almost a year so I went through all the versions before 4.0.
I personally upgraded to 4.0 and painstakingly downgraded to 3.1.3 through the steps provided.
Again, please post the steps you made so I can help you downgrade your firmware