iPhone2,1_5.0_9A334_Restore.ipsw <- this is the correct software for iPhone 3GS, so are you sure you have the right one, why im telling this, i had the same problem until i discovered that i had the wrong ipsw file, so i downloaded this, and viola, worked fine.. 🙂
And if you say you have the latest itunes, it should not be a problem at all..