Hmm, I hate trying to debug things like this
lol
Are you saying that on your server, if you did a ulx removeuserid on his steamID, then he joins, he would be able to join successfully? What happens when you give him access while/if he's in the server?
Yes, this sounds like an obvious client issue-- How does he "uninstall and reinstall" garrysmod? Perhaps you could make sure he does the following steps exactly to make sure he did it properly:
1) Close gmod (obviously)
2) Verifies his gmod game cache/integrity/steam stuff- whatever it's called
3) Renames, moves, or deletes his \steamapps\<username>\garrysmod\ folder.
4) Runs gmod, lets it regenerate the garrysmod folder and put all of the default files in.
5) Join any server using ULX/ULib (before installing any addons or moving any config/data files back to his new gmod folder)
If THAT doesn't work, then let me know-- It could be something on the server (??) preventing his join. I can set up a vanilla server with just the ULX/ULib svn installed, and he can try joining with the fresh version of gmod installed described above.