iTunes – Official List for iTunes/iOS Version Compatibility

That specific error is clearly spelled out on the general iOS error charts - http://support.apple.com/kb/TS3694

Saying that it didn't get a useful response is a bit vague.

iTunes requires a specific, signed, affirmative response from the apple servers before it will proceed. This is clearly by design. Additionally it checks the version of your iTunes and is asking you to get a newer version.

You may not want to upgrade iTunes as some people dislike some of the changes, but it looks like that's the cause here assuming you really removed all the umbrella changes properly. It also might ask for a newer iTunes but the problem isn't actually that.

There is a whole set of things to check at the top of the main article: security software, iTunes store tests, using old or modified .ipsw files.

It might be good to set up a new user on the windows os and see if you can download 4.3.3 cleanly (or find a pristine copy on the intertubes) and try the restore and debugging of the hosts file from a cleaner start.

You can use iOSSearch, a free tool to find apps in the iTunes store which are compatible with iOS 3.1.3. This is a non-commercial page I made.

Note: the app store has recently been updated to allow downloads of last compatible versions but it appears that this only provides apps which are compatible with iOS 4.