Sua rede estava funcionando até seus usuários começarem a atualizar o windows para o Windows 10?!
Isto ocorre pq a versão do protocolo SMB do windows 10 é diferente da do Linux/Samba inferior a versão 4.2 (parece que na versão 4.3 isto ja foi resolvido).
Para resolver o problema, uma configuração deve ser feita no cliente:
No windows, abra um prompt com poderes de administrador (CMD) e ative o SMB1:
sc.exe config lanmanworkstation depend= bowser/mrxsmb10/mrxsmb20/nsi
sc.exe config mrxsmb10 start= auto
Desative a versão SMB2/3
sc.exe config lanmanworkstation depend= bowser/mrxsmb10/nsi
sc.exe config mrxsmb20 start= disabled
Reinicie o computador
o processo original esta descrito aqui:
https://support.microsoft.com/en-us/kb/2696547
e aqui:
http://www.tenforums.com/network-sharing/31136-samba-shares-dont-show-up-windows-10-network.html