Matt,
Is your service URL using the fully qualified domain name (FQDN)?
For instance, this is an example of a FQDN:
ServerName.domain.com/arcgis/rest/services
This example is not qualified with the domain name:
ServerName/arcgis/rest/services
When outside your domain you'll need to use the FQDN for that resource to be located. Another comment in this thread mentioned using the IP adderess which is also an option. IF you take the applications out of the equation, can you simply reach the REST endpoint for that service URL?
Thanks,
-Dan