iTunes Store Problem Solved!

This is amazing. Somehow I managed to solve the problem (at least for my situation).

I am using an Alcatel SpeedTouch 510 DSL modem/nat-router/firewall, and I added the following firewall rule:

:firewall rule create chain=forward index=3 srcintfgrp=wan prot=tcp syn=yes ack=no action=drop

Basically this drops all TCP packets which arrive out-of-state on the WAN interface.

Not only did this solve my iTunes Store problem, it also made my Internet connection much faster (let me rephrase that - it is finally as fast as it should have been from the beginning. It has been kinda slow for a long time, I guess I just got used to it.)

My guess is that my ISP is doing some sort of traffic shaping/QOS, and maybe that's why a lot of packets arrive out-of-state. So if you have a similar problem, you might be able to solve it by putting the packets back in order or dropping out-of-state packets before they get to your iTunes (i.e. on the firewall/router in front of your computers).