Была точно такая же проблема на выходных. Полдня копался
Решилось переписыванием конфигов с арча.
Мешал фаервол сначала, (был установлен firestarter). Отключаешь - появляется сетевое окружение. Включаешь - дальше "сеть Windows" не видит. Снес фв.
Однако решилось не столько сносом firestarter, сколько тупо накрыл рабочим конфигом из арча.
Могу сейчас выложить с работы конфиг (на работе Ubuntu, конфиг остался с Ubuntu 7.10. При апгрейде на 8.04 не менялся). Все работает под ним. Поменяете только имя компа, р.группы и пути к шарам. Если нужен будет доступ на запись в шары, поменяйте writable no на writable yes.
У меня такое странное ощущение, что они в конфиг добавили какой-то хитрый пареметр, который я так навскидку не отловил. Но конфиги по количеству раскомментаренных и укзанных параметров заметно отличаются. Чем они там думают, не понятно.