Internet Connection Problems over Cellular

which rules out the URL being blocked upstream

Not necessarily. As one of the commenters pointed out, you do not indicate how you are using this URL in your app. If this is an HTTP request, and it works in a browser but not your app, try changing the User-Agent HTTP header of your request to match the one from the browser.

You have provided no error log, but from experience I have run into a few inconsistencies when connecting to a server.

Using HttpsUrlConnection a SNI header is set on HoneyComb and above but not on previous versions, which can alter how the server responds. To add to this there are some general SSL handling inconsistencies between API levels, such as handling of wildcard domains in a certificate is buggy in some api levels.

Second some phones/api levels add a header to HttpUrlConnection requests that specifies time the request was sent like so:

X-Android-Sent-Millis=1353085024868

Some servers seem to use these headers to detect mobile traffic and alter the response.

I had problems when using a dual-simcard. Do you have more devices connected? Try to shut them down.