I have the same problem using shutdown.exe to shutdown remote computer. Somehow I managed to fix this by adding NETWORK to the allowed user/group to perform "force shutdown from a remote system" on the local policy of the machine you are trying to shutdown.
1. Logon to the remote machine as administrator (the computer you want to shutdown remotely).
2. run "secpol.msc" > local policies > user rights assignment > force shutdown from a remote system
3. Add NETWORK
Hope this help.