That would be my question as well...what is the xp_cmdshell doing? And is it a different command at times since it fails intermittently. Or is it possible the xp_cmdshell doesn't execute at times (and why it succeeds other times).
If you have any other error codes, SQL state, those can sometimes point to where the issue may be with the access denied.
The table locking likely has nothing to do with whatever is happening with the xp_cmdshell errors. I realize it could but I doubt (hope) you aren't using xp_cmdshell to execute queries using some other program.

Sue