Is NetBIOS over TCP/IP enabled on the machines?
On the workstations (2k and xp) yes.

SirDice: The computer browser service is disabled on all workstations.
I did see an error in the event log on the NT 4 box that said it beleives it is the master browser and it really is not. That is the problem?

Restart the computer browser service on one of the Active Directory servers to force a new election?