Are you running a WINS server? I believe OS's like win9x and NT need WINS enabled to run some NetBIOS things like network browsing. 2k and XP rely only on DNS for everything, and if its a 2k network, then you no doubt have DNS. This would explain your problem. Unless you ARE running WINs, then the problem is of course not this...if you ARE running WINs, let me know some more about your environment.
Hope this helps!