I have followed the force.com documentation to create a SAML assertion sent from my Identity Provider to Salesforce which is configured to expect this incoming SSO response. My assertion looks just like the sample XML including the Signature. When I use an external tool (two actually) to validate the signed assertion (generated using the private key by my solution) using the public key certificate I've installed on Salesforce, the assertion validates just fine.

But when Salesforce receives this same signed assertion, it throws an error. When I use the validation tool, I get the following error (with the cert name snipped out):

The XML assertion looks like this (with sensitive parts snipped):

<samlp:Response ID="_26b1076a323642a78c4199a855f8e1bb"
IssueInstant="2013-01-14T21:21:46Z" Version="2.0"
xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion"
xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol">
  <Signature xmlns="http://www.w3.org/2000/09/xmldsig#">
    <SignedInfo>
      <CanonicalizationMethod Algorithm="http://www.w3.org/TR/2001/REC-xml-c14n-20010315" />
      <SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1" />
      <Reference URI="">
        <Transforms>
          <Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature" />
        </Transforms>
        <DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1" />
        <DigestValue>[snip]</DigestValue>
      </Reference>
    </SignedInfo>
    <SignatureValue>
    [snip]</SignatureValue>
    <KeyInfo>
      <KeyValue>
        <RSAKeyValue>
          <Modulus>[snip]</Modulus>
          <Exponent>AQAB</Exponent>
        </RSAKeyValue>
      </KeyValue>
    </KeyInfo>
  </Signature>
  <saml:Issuer Format="urn:oasis:names:tc:SAML:2.0:nameid-format:entity">
  https://[snip]</saml:Issuer>
  <samlp:Status>
    <samlp:StatusCode Value="urn:oasis:names:tc:SAML:2.0:status:Success" />
  </samlp:Status>
  <saml:Assertion ID="_92d3c65bd6544b7eb514b9b0e4321ffd"
  IssueInstant="2013-01-14T21:21:46Z" Version="2.0"
  xmlns="urn:oasis:names:tc:SAML:2.0:assertion">
    <saml:Issuer Format="urn:oasis:names:tc:SAML:2.0:nameid-format:entity">
    https://[snip]</saml:Issuer>
    <saml:Subject>
      <saml:NameID Format="urn:oasis:names:tc:SAML:1.1:nameid-format:unspecified">
      anybody.student@[snip]</saml:NameID>
      <saml:SubjectConfirmation Method="urn:oasis:names:tc:SAML:2.0:cm:bearer">

        <saml:SubjectConfirmationData Recipient="https://login.salesforce.com/?saml=Mg[snip]rq"
        NotOnOrAfter="2013-01-14T21:26:46Z" />
      </saml:SubjectConfirmation>
    </saml:Subject>
    <saml:Conditions NotBefore="2013-01-14T21:16:46Z"
    NotOnOrAfter="2013-01-14T21:26:46Z">
      <saml:AudienceRestriction>
        <saml:Audience>https://saml.salesforce.com</saml:Audience>
      </saml:AudienceRestriction>
    </saml:Conditions>
    <saml:AuthnStatement AuthnInstant="2013-01-14T21:21:46Z">
      <saml:AuthnContext>
        <saml:AuthnContextClassRef>
        urn:oasis:names:tc:SAML:2.0:ac:classes:unspecified</saml:AuthnContextClassRef>
      </saml:AuthnContext>
    </saml:AuthnStatement>
    <saml:AttributeStatement>
      <saml:Attribute Name="portal_id">
        <saml:AttributeValue xmlns:xs="http://www.w3.org/2001/XMLSchema"
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:type="xs:string">06[snip]VT</saml:AttributeValue>
      </saml:Attribute>
      <saml:Attribute Name="organization_id">
        <saml:AttributeValue xmlns:xs="http://www.w3.org/2001/XMLSchema"
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:type="xs:string">00[snip]dA</saml:AttributeValue>
      </saml:Attribute>
    </saml:AttributeStatement>
  </saml:Assertion>
</samlp:Response>

The certificate we are using to sign the assertion is self-issued, not from a certificate authority. But I can't find anything that says this is bad.

Does anyone know of any particular requirements for signing an assertion that are not covered in the documentation? I cannot find anything else to try changing!!!