PSexec is not connecting to machine using supplied username and password

Solution 1:

This is because psexec still tries to access the ADMIN$ share with your local credentials, before executing your command as another user. According to this thread, you can cache credentials before executing psexec:

cmdkey.exe /add:MACHINE_NAME_HERE /user:MACHINE_NAME_HERE\Administrator /pass:PASSWORD_HERE 
psexec.exe \\MACHINE_NAME_HERE -i notepad
cmdkey.exe /delete:MACHINE_NAME_HERE

I added -i, since you specified running notepad here. Without the -i, notepad will sit idle with no interacton. Also, please remembet that, when you use -u, psexec will send the password in plaintext.