Cara, isso tem haver com os registros WINS que tem um certo tempo de vida, o que vc vai precisar fazer a "forçar" essa atualização.
Pare o samba, Delete os arquivos "browse.dat" e "wins.dat", agora restart o samba.
Por default esses arquivos ficam em:
/var/cache/samba
mas você pode verificar a sua localização no parâmetro "lock directory" no smb.conf
Espero ter ajudado!