I'm running Windows 7, and normally the Services console can be open without affecting creation and deletion of services. But it wasn't even open anyway, yet something was still locking the service control manager.
I just couldn't figure this out...
Until I realized, some time later, that the Windows Update icon had been visible for a few days. I'd delayed installing the updates because I didn't want a reboot. So I installed them, rebooted the machine, and hey presto! I can once again uninstall and reinstall the service repeatedly without problems...