[exo]

Т.е. это может быть проблема не с серваком? »

на нем тоже должно быть включен LLDT Mapper.
Ну и проверьте стандартную службу computer browser.
но лучше у всех настроить LLTD.
на самих компах как сетевое окружение отображается?