Can't connect to Samba server via FQDN despite it resolving to the correct IP address

I'm really hoping that you guys can help me with a really weird problem I'm having with a new Samba server. I can connect to the server just fine via its IP address. I can also connect with its short hostname.

On one client, I can ping the server using serverhostname.internaldomain.com and the name resolves to the correct IP address. I can even connect to the server via SSH. The problem is when I try to access it over Samba I get the error "0x80070035: The network path was not found." Every other client (that I've checked so far) can connect just fine using the FQDN.

Nothing shows up in the logs of the Samba server, so I'm guessing it's a name resolution problem of some kind but I'm not sure what is going wrong. The name resolves fine when pinging it or connecting via SSH. If I set up a DNS record that maps somerandomstring.internaldomain.com to the server's IP I can connect fine.

There was a previous Samba server with the same hostname and IP address. Is it possible Windows is somehow "remembering" that server and thinking the change is somehow a security problem?

I don't have any firewall software running on the client.

Problem solved! It turns out Windows gives really bad error messages. There was some old credentials for the server stored on the computer and that seemed to cause the connection to fail. After opening "Credential Manager" and deleting the old credentials I can connect successfully, although I now get a different error when I actually try and log in "A device attached to the system is not functioning."