Yeah, after 45 minutes of downloading and more of installing - then it says, can't install because incompatible - huh???? I thought the 3Gs was okay.
Any suggestions?
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..
Restore on a different computer. I wanted to restore my new my new 4S because I was having syncing problems and was getting the same error. After a fresh restore my problems disappeared.