Are you creating the .msi yourself? If so, what are you using to create the .msi? If not, have you looked into:
By default, Windows blocks the installation of signed code if it has an invalid digital signature.
* If code has an invalid signature, it usually means that the code has been changed since it was signed. When this happens, Internet Explorer considers the code to be unsigned, since someone might have tampered with it. By default, Internet Explorer blocks ActiveX applications that are unsigned that come from the Internet zone. This extends that functionality so that it applies to all code with invalid signatures.
Users will find when launching an .msi (installer) via Internet Explorer or by saving the installer to disk before running, they will receive a security warning: "The publisher could not be verified. Are you sure you want to run this software"? This can be turned off by deselecting "Always ask before opening this file". This does not happen if launched using either Netscape or Mozilla.
Also, if this is not a package you are creating, I would look into the validity of the install package/check with the vendor.