Let me tell you this problem was infuriating for me. Flavius you saved my sanity. In every thread I read you were in there helping out. It took me awhile and many different methods but I finally nailed it down.
I was missing the installer so I searched for it on my comp and found 3 different copies by going to c:\windows\winsxs and then searching for trustedinstaller.exe. I then copied the files to the desktop and placed the largest one first in the c:\windows\services folder. Then I did the registry fix that Flavius has recomended. It did not work but I did get a new error in windows update.
At this point I went back into the c:\windows\services menu and deleted the version of trustedinstaller that I had placed in there and tried another one. This one did the trick. Everything is now working as normal.
Again I can't say how much I appreciate your efforts Flavius. Bravo!