Could not start PSEXESVC service on [MachineName]: Access is denied

Use the command in this way instead:

PsExec.exe -u [domain]\[username] -p [password] \\[Machine Name] cmd

For some reason, PsExec tries to start "PsExeSVC" on the remote computer using your local credentials instead of the domain credentials specified hence the "access is denied" error.

On the other hand, when you specify the credentials first, it works as expected.