The Client
The client has disabled "Run components not signed with Authenticode" either by choice or through a group policy setting.
The Error message
PLATFORM VERSION INFO
Windows : 5.1.2600.196608 (Win32NT)
Common Language Runtime : 2.0.50727.3603
System.Deployment.dll : 2.0.50727.3053 (netfxsp.050727-3000)
mscorwks.dll : 2.0.50727.3603 (GDR.050727-3600)
dfdll.dll : 2.0.50727.3053 (netfxsp.050727-3000)
dfshim.dll : 2.0.50727.3053 (netfxsp.050727-3000)
SOURCES
Deployment url : http://[ServerAddress]/[ApplicationName].application
Server : Microsoft-IIS/7.0
X-Powered-By : ASP.NET
Deployment Provider url : http://[ServerAddress]/[ApplicationName].application
ERROR SUMMARY
Below is a summary of the errors, details of these errors are listed later in the log.
* Activation of http://[ServerAddress]/[ApplicationName].application resulted in exception. Following failure messages were detected:
+ Your Web browser settings do not allow you to run unsigned applications.
COMPONENT STORE TRANSACTION FAILURE SUMMARY
No transaction error was detected.
WARNINGS
There were no warnings during this operation.
OPERATION PROGRESS STATUS
* [2010-01-25 13:35:51] : Activation of http://[ServerAddress]/[ApplicationName].application has started.
ERROR DETAILS
Following errors were detected during this operation.
* [2010-01-25 13:35:54] System.Deployment.Application.InvalidDeploymentException (Manifest)
- Your Web browser settings do not allow you to run unsigned applications.
- Source: System.Deployment
- Stack trace:
at System.Deployment.Application.ApplicationActivator.BrowserSettings.Validate(String manifestPath)
at System.Deployment.Application.ApplicationActivator.PerformDeploymentActivation(Uri activationUri, Boolean isShortcut, String textualSubId, String deploymentProviderUrlFromExtension, BrowserSettings browserSettings, String& errorPageUrl)
at System.Deployment.Application.ApplicationActivator.ActivateDeploymentWorker(Object state)
COMPONENT STORE TRANSACTION DETAILS
No transaction information is available.
Links
http://support.microsoft.com/kb/974620
http://msdn.microsoft.com/en-us/library/ms996418.aspx
The Solution
Add 2 Prerequsites to your ClickOnce Application and publish like
.NET Framework 2.0
Windows Installer 3.1
The client problably already has these installed but insted of running the .application fil it will run the setup.exe when the client push the install button.
The first security warning is for the setup.exe file and looks somthing like this.

After the client pushes the Run button, a new Security warning appears.

This security warning displays the publisher name, but most interesting is the More opiton. Expanding this gives some options we didn't have before.

The client now has the posiblity to always trust software with your certificat, by default Ask me every time is selected but if the client select Always run software from xxxx, the certificat will be added to your Trusted Publishers certificate store.

The next time the client gets updates or has to install new software with this certificate, there will be not prompt or ecurity warning, and thus the client has accepted you as a trusted software provider.
I hope this blog will help others with this problem, since I have used hours researching this problem.