I'm having the same problem. Without any apparent changes to my system (PC A), now when I try to use PSEXEC I get the error you mentioned. Also, from another PC (PC B), I can run PSEXEC with the same credentials and no error. So, from PC A I get the error, and from PC B no error.
Trying to run the script below I get the error:
psexec.exe -s -i \remote-machine cmd
Error deriving session key: object already exists.
Any updates on this problem?