Also, check your bindings orders. I had tons of headaches until I worked this out. Right click My Network Places and select properties. Click on the Advanced heading and then click on Advanced Settings. Here you are.
Basically what binding orders do is tell Win 2k which protocol to use first when trying to find a resource (computer, printer, whatever). Choose the protocol that you want to use for your networking and make sure it is the first one up there in the list. I had the same problems that you are having, however I could search for a computer and find it though. HHMMMMM... Well, tell us if this works for you.
LUCK!!!