NT and 98 workstations looking for 2000

What would cause various NT4 and 9x workstations to lose visibility of a 2000 server unless a fully qualified domain name is used? I am thinking a WINS issue…