I'm an avid iTunes buyer, and even with a 5MB connection to the internet, the store has become very intermittent. I click the store icon, and it loads 95% and then halts. Then it I have to click the home button several times to get it to finish. It's very frustrating. When I want to authorize music on my computers, it often fails. When I click to download a free song, it tells me the song is being modified, and can't be downloaded now.
This behavior has been the case at multiple locations, and even the Apple store itself has this problem.
No firewall. No router blocking.