An error occurred when verifying security for the message

This ended up being an problem on the consuming side, not with the service itself. Software AG's webMethods 8 was consuming this server but there was no Security Handler added to the service so the credentials were not being added to the header thus resulting the in the aforementioned error.

I was getting this same error message and it turned out to be due to a time difference between my workstation machine and the server hosting the WCF service. The server was about 10 minutes behind my machine and WCF security doesn't seem to like that very much.

To find the root problem I turned on serviceSecurityAuditing in the server's config file. Add the following to the configuration/system.serviceModel/behaviors/serviceBehaviors/behavior section for your service:

<serviceSecurityAudit 
    auditLogLocation="Application" 
    serviceAuthorizationAuditLevel="Failure" 
    messageAuthenticationAuditLevel="Failure" 
    suppressAuditFailure="true"/>

The following site was helpful in figuring this out:

http://blogs.microsoft.co.il/blogs/urig/archive/2011/01/23/wcf-quot-an-error-occurred-when-verifying-security-for-the-message-quot-and-service-security-audit.aspx

I had a similar issue. I was building my datetime formatted strings using my local time, but my service/server was expecting GMT.

I needed to get the GMT time (JAVA):

final Date currentTime = new Date();    
final SimpleDateFormat sdf = 
new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss'.000Z'");
sdf.setTimeZone(TimeZone.getTimeZone("GMT"));
System.out.println(sdf.format(currentTime));

Another cause of this message is when some of your machines are not synchronized in time. WCF, by default, allows a five-minute gap; beyond this, it throws an error if things are out of synch.

The solution is to synch all your machines. time.windows.com is notorious for not working, so I suggest using something else. (If you're in a corporate environment, a local domain controller may be the correct choice here.)