||OK, I've just been through this same problem. ArcGIS Server running on Windows Server 2003, trying to connect over a network domain. With the ArcGIS Server SP AND the DCOM patch installed we still couldn't contact ArcGIS Server.
Try this: Go to the Computer Management app (explore, right-click on "My Computer", choose "Manage"), expand "Local Users and Groups", click on "Groups", add all domain users to the "Distributed COM Users" group. For my network, all domain users is "Domain Users", check with your Systems Admin for what it is on your network. Or if you only want specific individuals to have access then just add them individually to this group.
Hit apply and everything should work. No need to restart or logoff & login but you can if you're superstitious. Be sure you have the Server and Container objects (whatever you named them in the post-install) in the Users group. The Server object should also be in the agsadmin group. Neither of these need to be in the Distributed COM Users group.
Another workaround is to add users to the Administrators group. This is obviously a bad long-term solution, especially if you're running an internet application or have a wireless access point near your building. But it will at least allow you to develop if the above solution doesn't work for you.