Yes, upgrading the Mac to Leopard will work.
Each new iDevice has certain identifiers (model number, etc.). When Apple releases a new one, the old version of iTunes would need an update to recognize it. (Sometimes this even happens with new device OS/firmware versions.) They bundle these updates with feature and bugfix updates, so you're stuck with a new version.
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.
Best Answer
Apple have now released iOS 4.3.5, so they may have disabled the authentication for 4.3.4, as they do with all legacy versions of iOS.. Try downloading and installing iOS 4.3.5.