So a friend of my wife's computers were not showing the iTunes store after the update to 10.4.1.10 on both 64 and 32 bit platforms, on Vista and Win 7. The only thing in common between the two machines was McAfee offered by Verizon.
As it turns out you have to do a "netsh winsock reset" from an administrator command prompt, and then reboot. McAfee seems to complain that something has been removed after you do that, and telling McAfee to fix the problem might screw up iTunes again, but I'm not sure. Once I solved the problem I moved on to other things so I didn't do further testing. Just something to be aware of.