если пользователей много, то для такого объема лучше иметь домен. такая проблема возникает и в домене, но только при кривом включении компа в домен. посмотри логи на клиенте, если на сервере нет. проверь также работу DHCP, WINS.