Picking off some other simple problems, the machine name is under 15 characters, and all alphanumeric, right? No spaces or other special characters?
If you are using WINS, every station on your LAN should be using WINS, and all pointing at the same server.
I assume you can ping your problem box from other machines, and the problem box can ping everyone else. If this is not the case, look for a cable problem, or a wrong IP address or wrong subnet mask.
Given all that, try these tests. Assume the box name is FRED in these examples, and that its IP address is 192.168.0.42:
First, test whether or not some other station can see your problem box. On another box, click Start, Run, and type in \\192.168.0.42 and click OK. Does the content of FRED show up, or do you get an error message? If the error message, the problem probably in the protocol stack. Remove and reinstall NETBEUI.
On another box, click Start, Run, and type in \\FRED and click OK. Does the content of FRED show up, or do you get an error message? If the error message, your name is not being recognized. Check the WINS database and see what is there. Check that the node type is set to hybrid, so that name resolution is actually using WINS.
Trying the tests on FRED, looking to connect to an other station will tell you if the protocol stacks on FRED are OK. If everything works, it is time to look for wierdness. Get a copy of tweakui from www.download.com (or wherever), and look at the setting that makes the box invisible to the network. There is a registry key for this, but I do not have it, and tweakui is easier.
Another longshot:
a) make very sure that your workgroup name is exactly the same as the domain name (no trailing spaces).
b) put anentry in your lmhosts file for the domain controller, using the #PRE and #DOM: tags.
This should force the station to find the domain.
Good luck.