A commonly overlooked step in the configuration of an ArcGIS Server is that you need to tell the server what its name is to the outside world. You see, on an internal network your computers might have names. As geologists we prefer names like "Eclogite", "Kyanite", "Harzburgite", etc... However, on the internet computers generally have more complicated names. These names are things like "services.azgs.az.gov" or "www.google.com" or "lab.usgin.org".

By default, your ArcGIS Server knows what the computer's internal name is. However, once you want to share your services with people outside that local network, you need to tell the ArcGIS Server how those other people will find it. You do this by editing a file called "rest.config". If you installed IIS and ArcGIS Server in all the default locations, you'll find this file at C:\inetpub\wwwroot\ArcGIS\rest\rest.config.

Look through the file and find all the URLs in it. Make sure that instead of using the computer's internal name, those URLs use the computers external name.

For more information, here are a couple of links:

ArcGIS Server Blog Post

ArcGIS Server v.10 Documentation