First, you must have the latest version of iTunes. So update your Windows version. If you are going to uninstall iTunes and reinstall it you MUST do it the right way - see: http://support.apple.com/kb/HT1925. If you didn't follow all of these steps it won't solve any problems.
In Windows, this problem is frequently caused by antivirus or firewall software interfering with the update. You probably don't have either of these on your Mac, however, so that is not as likely the problem.
The problem can be caused by a bad cable, or using a USB port on a hub rather than directly on the computer, or having other high data rate USB devices connected to the computer, so try disconnecting everything except the phone, keyboard and mouse.
The problem can also be caused by jailbreaking or removing the carrier lock on the iPhone. If this applies we can't help any further here in an Apple forum.
And finally, if the computer was ever used to hack any iDevice in the past the network database on the computer could be corrupted. Look in the hosts file (/etc/hosts on the Mac, c:\windows\system32\drivers\etc\hosts on Windows). If any lines contain gs.apple.com delete those lines.