Have you tried powershell?
We use powershell 2.0 and run remote commands on many servers
However the runtime user has to have enough rights on the target server to be able to stop and start tha target services
It's easiest to make the runtime user a local admin (usually we wind up executing other automated tasks on the servers)
Examples
CMD powershell
PARAMS - stop
set-service -computerName -name '' -status Stopped -passthru
PARAMS - start
set-service -computerName -name '' -status Running -passthru
one thing to watch out for is the service name being different from the name on target server
one may work over the other
Marc