Use Strtup Inspector to disable ITunes or anything connected with Itunes from starting with Windows.
Startup Inspector (manages startup menu – helps you identify aps in the startup menu so you can disable unnecessary programs from running in the background when they are not needed)
And
Startup Monitor (a small freeware ap available on the same page to notify you and require your permission for any program to add itself to your startup menu)
http://www.windowsstartup.com/download.phpAfter you disable ITunes from the startup menu reboot and try uninstalling it again.
If that isn't successful the information on the following MS Support page might help:
"Error 1719: The Windows Installer service could not be accessed" error message when you try to add or remove a program
http://support.microsoft.com/kb/315346/