WCF client Java interop - No Response Headers = MessageSecurityEx

Question

I am using a WCF client to communicate with a Websphere hosted web service. The service requires my message to be signed, but not encrypted. This is being done and works as expected. I can see in my trace logs that I get a valid response back from the service. However, it isn't making past the proxy becuase of the following error:

System.ServiceModel.Security.MessageSecurityException: Security processor was un able to find a security header in the message. This might be because the message is an unsecured fault or because there is a binding mismatch between the commun icating parties. This can occur if the service is configured for security and the client is not using security.

I've edited the binding to remove the timestamp and have verified that it is not being sent, however, I still get this error.

Here's what the header of my request looks like:

<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/" xmlns:u="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"&gt;
<s:Header>
<ActivityId CorrelationId="b0d474df-8b00-4c30-bd05-d1e478529ce4" xmlns="http://schemas.microsoft.com/2004/09/ServiceModel/Diagnostics"&gt;cb8e51de-83b4-4bfe-bf1c-fd92ce86f557&lt;/ActivityId&gt;
<o:Security s:mustUnderstand="1" xmlns:o="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd"&gt;
<o:BinarySecurityToken>
<!-- Removed-->
</o:BinarySecurityToken>
<Signature xmlns="http://www.w3.org/2000/09/xmldsig#"&gt;
<SignedInfo>
<CanonicalizationMethod Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"&gt;&lt;/CanonicalizationMethod&gt;
<SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1"&gt;&lt;/SignatureMethod&gt;
<Reference URI="#_1">
<Transforms>
<Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"&gt;&lt;/Transform&gt;
</Transforms>
<DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"&gt;&lt;/DigestMethod&gt;
<DigestValue>y14R/swQUSc8snEZWS/Y7+T+Qg8=</DigestValue>
</Reference>
</SignedInfo>
<SignatureValue>u0zzQtdp/2Jc+pj5+WwbyRGFuSqjMgk6SBqPIn2UMabiuevRX+RZbRPUPskJaWj5z91ut2yJaIn+OpczUenX42NescjhTsJjrvjYbuTJYFutRUxzKfikX61wBBYPFSuGtIcLImE+4dGcvhnAC3fHuH53LdaON+NApmFIqcSjckQ=</SignatureValue>
<KeyInfo>
<o:SecurityTokenReference>
<o:Reference ValueType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-x509-token-profile-1.0#X509v3" URI="#uuid-3d7c611f-a8ad-49c8-8d28-b3a63664adbc-2"></o:Reference>
</o:SecurityTokenReference>
</KeyInfo>
</Signature>
</o:Security>
</s:Header>

Here's what the header of my response look like. It has nothing in it, which I assume is not what the WCF client is expecting:

<s:Header xmlns:s="http://schemas.xmlsoap.org/soap/envelope/"&gt;&lt;/s:Header&gt;

Any idea how I can overcome this error?