You could also do it with PowerShell:
Get-WmiObject win32_service -filter "Name='My Service'" `
| Invoke-WmiMethod -Name Change `
-ArgumentList @($null,$null,$null,$null,$null, `
"C:\Program Files (x86)\My Service\NewName.EXE")
Or:
Set-ItemProperty -Path "HKLM:\System\CurrentControlSet\Services\My Service" `
-Name ImagePath -Value "C:\Program Files (x86)\My Service\NewName.EXE"