É possível que o Windows esteja usando um conjunto de credenciais em cache ao usar o \ Machine? Existe outro compartilhamento acessado nessa máquina usando um nome de usuário diferente, que não tem acesso ao \ share?
Cenário:
Domínio do Windows Server 2k3
Causas? Quais informações adicionais são necessárias para depurar isso?
Você verificou o DNS está correto? Com problemas de AD isso é mais frequentemente do que não o problema. Verifique se as máquinas cliente e servidor possuem entradas DNS válidas (e verifique o servidor DHCP).