Download notesping (if you have trouble finding it, it's on the downloads section of my Web site at "site extra's" --> "downloads") and use this utility to trace a route to your server using a variety of protocols.
If you can hit it via HTTP, but not Notes, check that NRPC traffic (port 1352) is able to get through your firewall to the server. Of course, you will ONLY be able to test this in the same environment as your users (e.g., dial an ISP and try to connect back in to your server).
This was first published in July 2005