In our network I have found that restarting the Workstation service on the client computer is able to resolve this problem. This has worked in cases where a reboot of the client would also fix the problem. But restarting the service is much quicker & easier [and may work when a reboot does not].
My impression is that the local Windows PC is caching some old information and this seems to clear it out.
For information on restarting a service, see this question. It boils down to running the following commands on a command line:
C:\> net stop workstation /y
C:\> net start workstation
Note – the /y flag will force the service to stop even if this will interrupt existing connections. But otherwise it will prompt the user and wait. So this may be necessary for scripting.
Be aware that on Windows Server 2016 (+ possibly others) these commands may also stop the netlogon service. If so you will have to add: net start netlogon