Also make sure that AOLServer is binding to an IP address and not localhost (127.0.0.1). You can run
nsd -ft nsd.tcl (the key here is -f option that tells to start in a foreground mode where AOLServer dumps the info to console window). AOLServer will print a message saying that nssock has started listening on ip address x (or something similar).
You can test Jonathan's DNS theory by doing ping machine_name from the box that cannot access your site. If ping works then it's something else. If it says something like "machine unknown" then it's DNS problem.
