And of course 2 seconds later I find a solution....
When logging in as Admin you also need the -h flag if you want full admin privileges.
So from my previous example:
PsExec.exe -i -h \XXXXXX -u XXXXXX\Administrator -p YYYYYY "C:\Program Files......."