WCF server error

Hi there,
I'm trying to call a WCF Service over HTTPS. When the client connects without a client certificate, everything works fine, but when we include the cert, the server throws this exception:

System.ServiceModel.Security.MessageSecurityException: Cannot resolve KeyInfo for verifying signature: KeyInfo 'SecurityKeyIdentifier
    (
    IsReadOnly = False,
    Count = 1,
    Clause[0] = X509IssuerSerialKeyIdentifierClause(Issuer = 'CN=XXXXXX,OU=ISD,O=XXXXXX,L=XXXXXX,ST=XX,C=US', Serial = '999999999')
    )
', available tokens 'SecurityTokenResolver
    (
    TokenCount = 0,
    )

Our outgoing WS-Security includes a Signature (Issuer Name & Serial) and Timestamp. Can anyone help?

        <wsse:Security xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd" xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
            <wsu:Timestamp wsu:Id="TS-14">
                <wsu:Created>2012-05-18T18:29:56.327Z</wsu:Created>
                <wsu:Expires>2012-05-22T05:49:56.327Z</wsu:Expires>
            </wsu:Timestamp>
            <ds:Signature Id="SIG-13" xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
                <ds:SignedInfo>
                    <ds:CanonicalizationMethod Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#">
                        <ec:InclusiveNamespaces PrefixList="wsa arr soap tem" xmlns:ec="http://www.w3.org/2001/10/xml-exc-c14n#"/>
                    </ds:CanonicalizationMethod>
                    <ds:SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1"/>
                    <ds:Reference URI="#id-310">
                        <ds:Transforms>
                            <ds:Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#">
                                <ec:InclusiveNamespaces PrefixList="arr tem" xmlns:ec="http://www.w3.org/2001/10/xml-exc-c14n#"/>
                            </ds:Transform>
                        </ds:Transforms>
                        <ds:DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/>
                        <ds:DigestValue>K1zy6D6PSsSvxYxYMborm2q2fMo=</ds:DigestValue>
                    </ds:Reference>
                </ds:SignedInfo>
                <ds:SignatureValue>
                    IhTwkXqX3tWfL+KdyRkfPeXxVcF+4hv7GMf9DaAACHUk3tN3DIklYvYhWeTmiFwFaMNO+rg1bG8n
                    wbjsGR1ZXbuVWht07vvftXORAsEwERA29tNiCj58KCcgIp7IlAG8y2XCzfk1mpoJVFyRWTfvhCBe
                    IblmUAcxUTLgSB57G/4=
                </ds:SignatureValue>
                <ds:KeyInfo Id="KI-DE28D25CC7A8B1C0F8133736579631620">
                    <wsse:SecurityTokenReference wsu:Id="STR-DE28D25CC7A8B1C0F8133736579631621">
                        <ds:X509Data>
                            <ds:X509IssuerSerial>
                                <ds:X509IssuerName>CN=XXXXXXXXXXXXXXXX,OU=XXX,O=XXXXXXXXXX,L=XXXXXXXXX,ST=XX,C=US</ds:X509IssuerName>
                                <ds:X509SerialNumber>9999999999999</ds:X509SerialNumber>
                            </ds:X509IssuerSerial>
                        </ds:X509Data>
                    </wsse:SecurityTokenReference>
                </ds:KeyInfo>
            </ds:Signature>
        </wsse:Security>