Ack, this is bugging me.
I've had this problem for a few weeks now! iTunes seems to insist that I am not connected to the internet, but I'm using the internet on the same computer on the same network to write this.
I've heard that I should check my firewall settings, but I don't see why that would help, I've been connected to the store with my current firewall for months!
Please help me. It's crucial that I can get to the iTunes store as soon as possible.