I have NONE of the above mentioned "security" software packages running - the ONLY thing that fixed it for me was the "netsh winsock reset" command.
I have tracked it down with maybe 17 installations and deinstallations.
With iTunes 10.4, the store was broken as soon as also Safari 5 was installed.
This is probably due to the new version of Apple Application support (higher than v1.5.2) - but I didn't take the time to do 5 more installations to find out when exactly the AAS gets installed, and by which installer.
With iTunes 10.4, a possible was to uninstall AAS v2.1.5 and to reinstall v1.5.2 - the store became accessible by that.
With iTunes 10.5, the AAS v1.5.2 could not be used anymore, and the store was broken.
I then ran into the suggestion to do the winsock reset, tried it - and bingo, the store works again.
Nevertheless, on another Windows 7 system where I tried it, the iTunes built-in diagnose erratically states that there would be no permission for iTunes in the Windows firewall - which is clearly wrong. But best thing is - the store IS accessible on that other system, despite the iTunes diagnose!!
On my main system, where only the winsock reset helped, iTunes diagnose told me that all tests were passed successfully, and it did NOT find that iTunes wouldn't be defined in the Windows firewall.
So, to put it short:
a) On one system iTunes diagnose states something would be wrong - but the store works.
b) On one system iTunes diagnose finds no problems at all - but the store will NOT work unless
a winsock reset was issued.
All tests were made with a previous complete uninstall of all Apple products, and a freshly rebooted system, to have a well defined state to compare.
Here's a summary:
Initial state: "blank" machine (no Apple products)
1.a Installed iTunes 10.4 - store works
1.b Installed Safari 5 - store is dead
1.c Uninstalled Safari - store remains dead
Initial state: "blank" machine (no Apple products)
2.a Installed iTunes 10.4 - store works
2.b Updated to iTunes 10.5 from within iTunes (ran Apple Software Update) - store dead
Initial state: "blank" machine (no Apple products)
3.a Installed iTunes 10.4 - store works
3.b Installed iTunes 10.5 using installation package from Apple web site - store dead
Initial state: "blank" machine (no Apple products)
4.a Installed iTunes 10.5 using installation package from Apple web site - store dead
Initial state: "blank" machine (no Apple products)
5.a Installed iTunes 10.4 - store works
5.b Installed Safari 5 - store is dead
5.c Uninstalled Apple Application Support v.2.1.5, reinstalled AAS v.1.5.2 - store works
Initial state: "blank" machine (no Apple products)
6.a Installed iTunes 10.5 using installation package from Apple web site - store dead
6.b Ran "netsh winsock reset", then reboot - store works
So it's clearly a problem of the Apple software - on NEITHER machine there's any software that would mess around with internet connections, ports, blocking things etc.