Хорошо, лог запросов на DNS сервер с IP машины смотрел?
Если лог напрямую не получается, попробуй что-нить подобное tcpdump запустить сразу после ребута на клиенте и потрогать проблемные места, потом посмотреть, что вообще там творится.
Я сильно сомневаюсь, что наутилус берет информацию из ППП, значит - откуда-то он её берет.