When you stored the authentication for that remote host are you adding the server name as part of the username (i.e, server\username)? If not, could you try doing that to see if it makes a difference? If that doesn't work, could you try following this KB article on the non-domain machine:
Once you've made that change, could you try the remote shutdown again? Did that work this time?