Hola,
Que raro... con los Win 9x confieso que he tenido problemas pero con los NT/XP para nada. Tenés algún servidor wins corriendo no definido en la configuración de SAMBA?
Podría ser un conflicto por algún cambio de nombre/máscaras o quién sabe, pero la verdad si vos decís que no se tocó absolutamente nada y de pronto dejó de funcionar es por demás extraño.
Podrías probar de hacer lo siguiente: Compartir un nuevo recurso desde la PC linux, configurar una tercera PC (física/vmware) que tenga una instalación limpia, agregarla como cliente SAMBA y ver que ocurre.
Quizás ayude en algo si posteas la sección "general" del smb.conf.
Lamento no ser más concreto, pero realmente no es demasiado fácil encontrarle una solución a un tema de redes sin poder estar presente
Saludos!