Are you able to connect to the Mobile iTunes store with 3G. If you didn't know before, you are now able to connect to the iTunes Mobile Store via 3G and even EDGE (2G).
Also, how many bars of 3G do you have? And what page on the App Store are you trying to access, or does this occur on all pages?
David