Windows cannot access the specified device, path or file with DFS -> right click explore works

So we have a DFS root and our users here map a drive letter to the
root. For some users, when they go to My computer and double click on
the mapped drive, they get tht error "Windows cannot access the
specified device, path, or file." A right click->open also does not
work. If we hit ok to that error, then right click on the drive and
choose explore, it opens the network drive just fine. Any ideas?

.