Right now I have a user who is able to use his domain credentials to log in to any server on our network, except one. The server that he cannot log in to allows other domain users to connect, but when he tries to connect it says that he is unauthorized.
When a user is locked out in an Active Directory environment, is it at the domain level or is it on a particular server?
Domain account lockouts are not per-member. They are domain-wide.
This user probably hasn't been added to the local administrators group (or the Remote Desktop Users group) on this particular server. The error message that you're describing is not the one that you would see if the account was locked.