первым делом рекомендую поставить на сервер collectd, настроить на сбор информации об IO, CPU, памяти и сети.
Как наберётся статистика - смотрите логи collectd в момент тормозов - какой-то из графиков будет перекашивать.
Т.е. - моё подозрение - что либо сетевая подсистема, либо дисковая сервера не справляются с одновременным стартом нескольких машин.
И ещё вопрос: в этой сети вообще что-то помимо Linux присутствует ? Если есть машины с Windows - проверьте их на вирусы. бывает и такое, что вирус "портит" сеть отправкой кривых ARP пакетов.