Error 1719 Windows Install Server could not be accessed

Hello Experts

I have a Windows 64Bit 2008 Terminal Services box.

I get the below error when i try to run an update to some software on the box.
Error 1719. Windows Installer service could not be accessed.  Contact your support personal to verify that it is properly registered and enabled.

In the event log i get
Event ID: 1013
Source: MsInstaller
Internal MSI error. Installer terminated prematurely.

Event ID: 11719
Source: MsInstaller
Error 1719.Windows Installer service could not be accessed. Contact your support personnel to verify that it is properly registered and enabled.

I have been able to install Office 2010 on this box without any problems.  I have even uninstalled the software i'm trying to update and reinstalled without any problems.  Only the programs updates seem to not work.

I have registered the DLLs for MsInstaller also.

I'm not sure what to do next.  This is a production server, i don't want to go playing around to much and break something else.  

Any idea's what i could do ?

Regards,
Thanks in advance for any help.