Can't access AppStore when connected via 3G
I also had a problem where the App Store was working on Wi-Fi, but not on 3G and 4G networks. I solved it by going into:

Settings → Mobile Data (also called Cellular). Under the heading Use Mobile Data For, enable App Store.