Here's something that worked for me.

Get SetACL.exe (Sourceforge, google for it)

Run the following on affected computers:
setacl -on hkcr\TypeLib -ot reg -actn ace -ace n:Everyone;p:full -rec yes

That will give full access to everything for everyone in the TypeLib branch of the HKEY_CLASSES_ROOT registry trunk. I don't see how this is a big security risk, given that it's only the TypeLib branch.