Microsoft KB article 823942 confirms this is a BUG and explains why this error occurs.
To workaround this problem Microsoft suggests to restart the computer before you reinstall the service.
You can attempt to re-install the service without rebooting the computer, in order to work around the problem close all open MMC snap-ins, especially the Services.msc.
The note to the KB article says:
If you first verify that the service is stopped, and then you quit the Microsoft Management Console (MMC) before you remove the service, you may be able to reinstall the service without restarting the computer.
For additional information please see Microsoft KB article 823942:
http://support.microsoft.com/kb/823942
As the article says this problem may occur if the following conditions occur in this order:
1. You install a service in a Windows Service application.
2. You remove the service by using a Windows Installer (.msi) file. Note To remove the service by using an .msi file, right-click the program icon for the .msi file, and then click Uninstall.
3. You reinstall the same service without first restarting the computer.
If you installed the service on a Windows 2000-based computer, you must restart the computer before you can reinstall the service.
In Windows 2000, services are not completely deleted until the computer is restarted. Although you do not receive a prompt to restart the computer after you remove the service, you must restart the computer before you reinstall the service.
Note
If you remove the service by using an executable (.exe) file, you receive a prompt to restart the computer.
