Такая же проблема была.
Решилось установкой парметра в smb.conf
remote announce = 192.168.0.255
Можно
remote announce 172.20.20.0.255 192.168.0.255
Пока не разобрался что там конкретно происходит :) (При этом, во втором случае, компы из внутренней сети, оказываются в броузлисте внешней, но, естественно только как некий мусор, потому что фактически доступа к ним через NAT обратно нету. Происходит ли такое в первом случае пока не выяснил )
Кроме того, в smb.conf указал, что samba должна быть local master browser (во внешней локалке она таковым может и не быть, а вот во внутренней, как я понял, должна)
И еще у меня стоит wins server = a.b.c.d - wins сервер во внешней сети, и wins proxy = yes, но это на броузинг нифига не влияет точно, потому что wins сервер другими вещами занимается.
Есть неплохая статья на тему броузинга компов, там написано про remote announce (причем в man smb.conf написано совсем другое...)
http://www.samba.org/samba/docs/man/Samba-HOWTO-Collection/NetworkBrowsing.html
Все это проделано с FreeBSD 5.3, Samba 3
Словеса для ищущих: Network Neighborhood My Network Places Samba Behind NAT firewall Computer Browsing