Is NetBIOS over TCP/IP enabled on the machines?

Make sure you don't have two master browsers. An NT box is likely to try to grab the master browser role regardless of the fact that there is a valid master browser on the subnet. It then plays havoc with WINS and NetBIOS. There's an article somewhere on MS about forcing a master browser out of it's role. I never used it but one of my employees told me about it when we had a similar problem.