Watch the user log into his workstation, and make sure he is logging in as the domain user for your domain, not a local user. If he is the local user and his user name and password do not exactly match his domain user name and password, he will not get access.
A way to check this: Put the user in domain admins. Create a separate folder that ONLY domain admins can access, have him log on, then try to access THAT folder. If he is not getting the domain permissions, he will not be able to access it.
You should also check the original folder for any specific permission denials. If, for example, you have a group named "goons" which you have denied access to the folder (by setting "no access"), if the user is in this group he will get no access, even if he might have access through the "everyone" or "domain admin" group.
Good luck.