When you open SQL Server's "Server Network Utility" what protocols are enabled? It sounds like you need Named Pipes enabled as that is what your error message is complaining about. I have TCPIP and Named Piples enabled.

Can you connect to this SQL Server instance from a remote machine using Enterprise Manager?

Another common problem I've seen is DNS server sending your connection requests to the wrong machine. I have a server right now that everytime I try to connect to it from one area of our network I actaully connect to a sales person's laptop and not the server I want. The DNS folks are looking into it, but most likely the DNS tables are just messed up. I figured it out by using remote desktop to make the connection and realized it was not the machine I was expecting. OK, I also kicked the guy off of is machine when I logged on and he was logged out, but that story is for another day...

I now you said you can't install SQL Server 2000 SP4 because you are running on NT 4.0, how about SQL Server SP3. I know on Windows2000 you had to be on at least SQL Server SP3 otherwise the network connections were disabled. I'm not sure what SQL Server's support is for NT 4.0.

-Tony