У меня похожая ситуация.

И дома и на работе больше года стоял ubuntu 8.10 Все работало как надо. Неделю назад поставил 9.04 и на началось.
И дома и на работе постоянно пропадает сеть. Пропадает и появляется. Сама. Это в общих словах. Теперь по пунктам.
Дома.
Прямое подключение к инету.
Инет настроил. По началу была такая фигня: при закачке скорость "взлетает" до максимума и падает на ноль. Снес NM и ручками настроил файл interfaces. Теперь скорость держится, но пропадает связь (Windows на этом же компе сеть не теряет и 8.10 тоже работала стабильно). Пропадает буквально на секунды, потом опять появляется. С помощью PINGа отловить потерю пакетов не удалось. Пингуется без потерь пакетов, но ИНОГДА ОЧЕНЬ долгий отклик. При работе в браузере частенько страницы не открываются. При этом никах сообщений об ошибках не выдается. Приходится по нескольку раз щелкать на сслыках, чтобы страница открылась.
На работе.
Такая же фигня. Тоже снес NM и руками настроил сеть. Основная сеть - под серваком вин. Прокси тоже под ней. С инетом симптомы один в один. При обращении к компам в сети тоже приходится по нескольку раз "стучаться". Происходят сбои при копировании файлов из локалки.
Куда копать? Какие логи смотреть? В основных ничего криминального не нашёл. Может я не знаю что именно нужно смотреть?
Еще немного и gajim у меня повесится