Well, it has to be one of a few things. Permissions for the command itself, which I think would result in another error. Command is not in the users path. Last that I can think of, something to do with the way it is mounted. So, I would do a:
ls -al /bin/mkdir
That would be assuming that mkdir is in /bin on your system. Then I would type in as that user:
/bin/mkdi
then hit tab twice. If that command is in your path, it should auto complete the whole command and add the "r" on the end. Then if all else fails, check out how the partition the directory is on is mounted. Just type in mount and look at the list. I would look for something obvious like mounted ro, read only, or something like that. If you use uuid's or something, make sure those are OK too. I don't use those so no idea what is correct or not but know they can mess things up when not set correctly.
If none of that works, I'm clueless. So, I hope that helps.