por lo menos en ubuntu gnome 10.04 32 y 64 bits y 9.10 32 bits te lo instala de por si, no se del resto,y por ahora siempre me encontro las las redes de mocosoft y tampoco tuve problemas agregando impresoras conectadas a otras maquinas con el mismo, por eso dije que me sonaba raro que no lo tenga instalado... aunque no digo que sea imposible tampoco
por otro lado tambien se me ocurrio que si la pc que sirve de puerta de enlace esta conectada directamente a internet sin router o switch y tiene dos placas de red lo mas probable es que alla hecho un bridge y no tenga una red interna por lo que no ve a la pc a la cual quiere ver sus carpetas compartidas.... ya que hasta donde tengo entendido windows no da soporte a multiples placas de red y dudo seriamente que alla generado una red interna desde windows donde routee de una placa a la maquina y de la maquina a internet, generando subdirecciones para ambas maquinas (ni siquiera se si es posible desde windows, estuve leyendo un poco de routing de una placa a otra de acuerdo a las direcciones desde dos para que coexistan 2 redes en una maquina con windows pero en la practica nunca lo pude hacer funcionar...)
ahora si si tiene un router atras de la maquina que le esta haciendo de puerta de enlace se supone que este la podria redirigir a la pc sin problemas siempre y cuando la pc lo este fowardeando con un ip aparte dentro de la red...
por eso estaria bueno que de un poco mas de info sobre su configuracion de su red para ver si el problema anda por ahi
espero que se entienda lo que queria decir
igual esto es solo una teoria que me surgio, falta informacion para confirmar...