First I would try to run a local elevation with:
Does that work for you?
"c:\your_path\psexec.exe" -i -s cmd.exe
OR
"c:\your_path\psexec64.exe" -i -s cmd.exe
You should get something like:
C:\Windows\system32>whoami /user
USER INFORMATION
----------------
User Name SID
=================== ========
nt authority\system S-1-5-XX
I have tried it on my computer which is in domain:
C:\app\tools\Sysinternals Suite>psexec -i -u "nt authority\network service" C:\Windows\System32\cmd.exe
PsExec v2.2 - Execute processes remotely
Copyright (C) 2001-2016 Mark Russinovich
Sysinternals - www.sysinternals.com
Couldn't install PSEXESVC service:
The network name cannot be found.
Make sure that the admin$ share is enabled.
C:\Windows\System32\cmd.exe exited on XXXX with error code -1073741510.
Producing:
Microsoft Windows [Version 6.1.7601] Copyright (c) 2009 Microsoft Corporation. All rights reserved.
C:\Windows\system32>whoami /user
USER INFORMATION
----------------
User Name SID
============================ ========
nt authority\network service S-1-5-XX
My guess based on this is that the message Couldn't install PSEXESVC service:
is connected to your network name.
Does it work for you if you try it this way?
"\\computer.domain.com\C:\app\tools\Sysinternals Suite\psexec.exe" \\computer.domain.com -u "domain\username" -p "passwd" -e -s cmd.exe
-i
switch, if that makes a difference?