Eu realizaria uma captura de pacotes para confirmar se está conectando ao computador desejado onde o compartilhamento está localizado quando o erro ocorre.
O comportamento muda se estiver usando um endereço IP em vez do nome abreviado do computador? Ou seja, sempre funciona se estiver usando o endereço IP? Ou se estiver usando um fqdn em vez do nome abreviado?
Você pode tentar isso de um cliente que tenha a versão mais recente dos componentes MRXSMB do cliente. Se sempre funciona em um cliente corrigido, pode ser um bug no Windows. Essas são publicadas aqui:
Lista de hotfixes atualmente disponíveis para as tecnologias de serviços de arquivos no Windows Server 2008 e no Windows Server 2008 R2