I have this same problem, 2 PC’s both running 2000 pro with almost identical configurations.
If I install NetBEUI everything seems fine (completely useless though because I use imaging over TCP/IP) but when I try to use TCP/IP with file and print sharing I get all the wonderful errors you’ve described.
Just for kicks I’ll write out everything I’ve tried (that I can remember)
Disabling my firewall
Changing workgroup names
Changing IP address
Changing subnet masks
Enabling and disabling Netbios (though it shouldn’t make any difference because I’m using the machines IP address rather than its name)
Enabling and disabling LMHOSTS
Giving the TCP/IP settings a default gateway (pointless I know)
Changing the DNS server (even more pointless)
Checking that file and print sharing is enabled
Checking that my client for MS networks is enabled
Pulling out the RJ45 connected to the cable modem and restarting my computer (I was getting desperate)
Things I’m going to try tomorrow that I have a sinking feeling will do nothing
Changing computer names
Uninstalling the network adapter driver and restarting the computer
Updating the network cards drivers (if I can find any)
Pulling out my switch and using a crossover cable
RE-INSTALLING WINDOWS
Just to go over the error again when I click on “Computers Near Me” I get “workgroup is not accessible. The list of servers for this workgroup is not currently available”
When I start > run \\compuer_name I get the proper folder but when I click on any of the shares “vol1 vol2 etc” I get “the network path was not found”
Same error if i put "\\192.168.0.1" which is my LAN NIC