I have run into this before.  You probably have a session of msiexec.exe
still running in the background.  If you start Task Manager, and view
Processes, you will probably see msiexec.exe running.  You will need to kill
this.  By doing this, I have sometimes gotten around the problem. But
remember other applications use the Windows Installer and it may have had an
interrupted install that has created the problem for the Windows Installer
application.  Hence the reference to "MSI (c) (C2:C7): Cleaning up
uninstalled install packages, if any exist"

If this doesn't work, I have also tried totally uninstalling TSM then tried
re-installing.  If that doesn't work, I have used the MS Windows Installer
Clean up utility... BE VERY CAREFUL using it.  It can be found on their
website.

Unfortunately some of these solutions will require a boot... a problem for
me in tackling my problem on a production server that could not be booted
just any old time!!!

Hope this helps.

Matt Adams
Tivoli Storage Manager Team
Hermitage Site Tech
Deloitte & Touche USA LLP
615.882.6861