ArcGIS server uses two windows user groups: agsadmin and agsusers, to control the access to the server. It works well without windows XP SP1 (possibly also on win2K). WinXP SP1 disables the remote activation of any DCOM object, and thus the ArcGIS client, like ArcCatalog or other program, can't access the server. The error message is something like the server machine is not running, which is misleading and incorrect.
To solve this, an additional step must be taken. The two groups, agsusers and agsadmin, must be explicitly granted the permission to remotely activate and run ArcGIS server. It can be done by opening Control Panel -> Administrative Tools -> Component Services, and on the left panel right click Component Services -> Computers -> My Computer to bring up the Properties box. Select COM Security and click on Edit Default for "Access" and "Launch and Activation" permissions. Add the two groups and allow remote launch and activation. This may require a reboot of the machine.
Another way doesn't need to reboot the machine. Go to Component Services -> Computers -> My Computer -> DCOM Config, right click on ArcSOM, and select Security tab. In "Launch and Activation Permissions" section, click Edit... and then add the user groups in and grant them remote launch and activation permissions.