Eu finalmente resolvi esse problema:
Depois de descobrir que todas as máquinas tinham o mesmo problema, era óbvio que era um problema do servidor remoto e não das máquinas clientes. Então, dei uma olhada no histórico de comandos dos servidores remotos e descobri que um colega instalou o suporte acl, o que fez com que o samba se recusasse a funcionar corretamente. Eu precisava adicionar suporte a acl ao smb.conf
assim:
[myshare]
nt acl support = yes
e reiniciei o serviço samba na minha máquina remota Debian com
/etc/init.d/samba restart
e funcionou como um encanto então.
Graças ao link que me deu a solução.