Hello Everyone,
After upgrading to Lion (10.7.5) on my MAC Book Pro, I started having the same issue: Could not connect to iTunes + "Cannot connect to App Store" AND clicking Software Updates would yield a network connection error after 2-5 minutes.
For days! I looked EVERYWHERE for a fix and tried everything! to no avail. Finally I started looking at my WiFi settings... the configuration looked pretty normal until I got to the Proxies tab. For Select a protocol to configure, I had Auto Proxy Discovery enabled/checked. After I unchecked/disabled this box, clicked OK, then Apply on the Network box, App Store, iTunes AND Software Updates worked again!!! 🙂
So whether you're using a LAN or WiFi connection, click the Advanced button (on Network) and review your configuration.
Hope this helps.