Microsoft One-Click Installer - User Never Prompted for Trust

I wrote an Excel add-in for a client that does some custom things for 5 users. I wrote it with VS2012 and the interop assemblies for Excel 2010. I published the add-in with the MS one-click publisher, zipped up the contents, and sent it to these 5 users. They are (seemingly) only able to install the add-in at random. Some users have been successful, while others get an error message. Some more info:

• The users that are not successfully installing are never being prompted to trust the install. It takes them right to to the error message.
• I signed the code with just a local dev cert. I didn't use a verisign certificate or anything like that. I didn't figure that it would do anything, because their local file system is never allowing it to get to the prompt.
• First I made a batch file to configure the registry for inclusion list security. This did nothing.
• I haven't been able to replicate the error on any other PC, whether it's on my local network or not.

My guess is that they've got something in their security policy that prohibits access to these one-click installer files. Any ideas which one?

Here is the error message:

System.Security.SecurityException: Customized functionality in this application will not work because the certificate used to sign the deployment manifest for ThisAddin or its location is not trusted. Contact your administrator for further assistance.
at Microsoft.VisualStudio.Tools.Applications.Deployment.ClickOnceAddInTrustEvaluator.VerifyTrustPromptKeyInternal(ClickOnceTrustPromptKeyValue promptKeyValue, DeploymentSignatureInformation signatureInformation, String productName)
at Microsoft.VisualStudio.Tools.Applications.Deployment.ClickOnceAddInTrustEvaluator.VerifyTrustUsingPromptKey(Uri manifest, DeploymentSignatureInformation signatureInformation, String productName)
at Microsoft.VisualStudio.Tools.Applications.Deployment.ClickOnceAddInDeploymentManager.VerifySecurity(ActivationContext context, Uri manifest, AddInInstallationStatus installState)
at Microsoft.VisualStudio.Tools.Applications.Deployment.ClickOnceAddInDeploymentManager.InstallAddIn() The Zone of the assembly that failed was:MyComputer

I was in a pinch for time, so I exported the developer certificate and had them install it on their machines.