I've been having this problem for a while and it's driving me nuts.  I'm trying to create a client (in C# .NET 2.0) that will use SAML 1.1 to sign on to a WebLogic 10.0 server (i.e., a Single Sign-On scenario, using browser/post profile). The client is on a WinXP machine and the WebLogic server is on a RHEL 5 box.
I based my client largely on code in the example here: http://www.codeproject.com/KB/aspnet/DotNetSamlPost.aspx (the source has a section for SAML 1.1).
I set up WebLogic based on instructions for SAML Destination Site from here:http://www.oracle.com/technology/pub/articles/dev2arch/2006/12/sso-with-saml4.html 
I created a certificate using makecert that came with VS 2005.
makecert -r -pe -n "CN=whatever" -b 01/01/2010 -e 01/01/2011 -sky exchange whatever.cer -sv whatever.pvk
pvk2pfx.exe -pvk whatever.pvk -spc whatever.cer -pfx whatever.pfx
Then I installed the .pfx to my personal certificate directory, and installed the .cer into the WebLogic SAML Identity Asserter V2.
I read on another site that formatting the response to be readable (ie, adding whitespace) to the response after signing would cause this problem, so I tried various combinations of turning on/off .Indent XMLWriterSettings and turning on/off .PreserveWhiteSpace when loading the XML document, and none of it made any difference.  I've printed the SignatureValue both before the message is is encoded/sent and after it arrives/gets decoded, and they are the same.
So, to be clear: the Response appears to be formed, encoded, sent, and decoded fine (I see the full Response in the WebLogic logs).  WebLogic finds the certificate I want it to use, verifies that a key was supplied, gets the signed info, and then fails to validate the signature.
Code:
public string createResponse(Dictionary<string, string> attributes){
    ResponseType response = new ResponseType();
    // Create Response
    response.ResponseID = "_" + Guid.NewGuid().ToString();
    response.MajorVersion = "1";
    response.MinorVersion = "1";
    response.IssueInstant = System.DateTime.UtcNow;
    response.Recipient = "http://theWLServer/samlacs/acs";
    StatusType status = new StatusType();
    status.StatusCode = new StatusCodeType();
    status.StatusCode.Value = new XmlQualifiedName("Success", "urn:oasis:names:tc:SAML:1.0:protocol");
    response.Status = status;
    // Create Assertion
    AssertionType assertionType = CreateSaml11Assertion(attributes);
    response.Assertion = new AssertionType[] {assertionType};
    //Serialize
    XmlSerializerNamespaces ns = new XmlSerializerNamespaces();
    ns.Add("samlp", "urn:oasis:names:tc:SAML:1.0:protocol");
    ns.Add("saml", "urn:oasis:names:tc:SAML:1.0:assertion");
    XmlSerializer responseSerializer =
            new XmlSerializer(response.GetType());
    StringWriter stringWriter = new StringWriter();
    XmlWriterSettings settings = new XmlWriterSettings();
    settings.OmitXmlDeclaration = true;
    settings.Indent = false;//I've tried both ways, for the fun of it
    settings.Encoding = Encoding.UTF8;
    XmlWriter responseWriter = XmlTextWriter.Create(stringWriter, settings);
    responseSerializer.Serialize(responseWriter, response, ns);
    responseWriter.Close();
    string samlString = stringWriter.ToString();
    stringWriter.Close();
    // Sign the document
    XmlDocument doc = new XmlDocument();
    doc.PreserveWhiteSpace = true; //also tried this both ways to no avail
    doc.LoadXml(samlString);
    X509Certificate2 cert = null;
    X509Store store = new X509Store(StoreName.My, StoreLocation.CurrentUser);
    store.Open(OpenFlags.ReadOnly);
    X509Certificate2Collection coll = store.Certificates.Find(X509FindType.FindBySubjectDistinguishedName, "distName", true);
    if (coll.Count < 1) {
        throw new ArgumentException("Unable to locate certificate");
    }
    cert = coll[0];
    store.Close();
    //this special SignDoc just overrides a function in  SignedXml so 
    //it knows to look for ResponseID rather than ID 
    XmlElement signature = SamlHelper.SignDoc(
            doc, cert, "ResponseID", response.ResponseID);
     doc.DocumentElement.InsertBefore(signature,
            doc.DocumentElement.ChildNodes[0]);
     // Base64Encode and URL Encode
     byte[] base64EncodedBytes =
            Encoding.UTF8.GetBytes(doc.OuterXml);
     string returnValue = System.Convert.ToBase64String(
            base64EncodedBytes);
     return returnValue;
}
private AssertionType CreateSaml11Assertion(Dictionary<string, string> attributes){
    AssertionType assertion = new AssertionType();
        assertion.AssertionID = "_" + Guid.NewGuid().ToString();
        assertion.Issuer = "madeUpValue";
        assertion.MajorVersion = "1";
        assertion.MinorVersion = "1";
        assertion.IssueInstant = System.DateTime.UtcNow;
        //Not before, not after conditions 
        ConditionsType conditions = new ConditionsType();
        conditions.NotBefore = DateTime.UtcNow;
        conditions.NotBeforeSpecified = true;
        conditions.NotOnOrAfter = DateTime.UtcNow.AddMinutes(10);
        conditions.NotOnOrAfterSpecified = true;
        //Name Identifier to be used in Saml Subject
        NameIdentifierType nameIdentifier = new NameIdentifierType();
        nameIdentifier.NameQualifier = domain.Trim();
        nameIdentifier.Value = subject.Trim();
        SubjectConfirmationType subjectConfirmation = new SubjectConfirmationType();
        subjectConfirmation.ConfirmationMethod = new string[] { "urn:oasis:names:tc:SAML:1.0:cm:bearer" };
        // 
        // Create some SAML subject. 
        SubjectType samlSubject = new SubjectType();
        AttributeStatementType attrStatement = new AttributeStatementType();
        AuthenticationStatementType authStatement = new AuthenticationStatementType();
        authStatement.AuthenticationMethod = "urn:oasis:names:tc:SAML:1.0:am:password";
        authStatement.AuthenticationInstant = System.DateTime.UtcNow;
        samlSubject.Items = new object[] { nameIdentifier, subjectConfirmation};
        attrStatement.Subject = samlSubject;
        authStatement.Subject = samlSubject;
        IPHostEntry ipEntry =
            Dns.GetHostEntry(System.Environment.MachineName);
        SubjectLocalityType subjectLocality = new SubjectLocalityType();
        subjectLocality.IPAddress = ipEntry.AddressList[0].ToString();
        authStatement.SubjectLocality = subjectLocality;
        attrStatement.Attribute = new AttributeType[attributes.Count];
        int i=0;
        // Create SAML attributes. 
        foreach (KeyValuePair<string, string> attribute in attributes) {
            AttributeType attr = new AttributeType();
            attr.AttributeName = attribute.Key;
            attr.AttributeNamespace= domain;
            attr.AttributeValue = new object[] {attribute.Value};
            attrStatement.Attribute[i] = attr;
            i++;
        }
        assertion.Conditions = conditions;
        assertion.Items = new StatementAbstractType[] {authStatement, attrStatement};
        return assertion;
}
private static XmlElement SignDoc(XmlDocument doc, X509Certificate2 cert2, string referenceId, string referenceValue) {
        // Use our own implementation of SignedXml
        SamlSignedXml sig = new SamlSignedXml(doc, referenceId);
        // Add the key to the SignedXml xmlDocument. 
        sig.SigningKey = cert2.PrivateKey;
        // Create a reference to be signed. 
        Reference reference = new Reference();
        reference.Uri= String.Empty;
        reference.Uri = "#" + referenceValue;
        // Add an enveloped transformation to the reference. 
        XmlDsigEnvelopedSignatureTransform env = new    
            XmlDsigEnvelopedSignatureTransform();
        reference.AddTransform(env);
        // Add the reference to the SignedXml object. 
        sig.AddReference(reference);
        // Add an RSAKeyValue KeyInfo (optional; helps recipient find key to validate). 
        KeyInfo keyInfo = new KeyInfo();
        keyInfo.AddClause(new KeyInfoX509Data(cert2));
        sig.KeyInfo = keyInfo;
        // Compute the signature. 
        sig.ComputeSignature();
        // Get the XML representation of the signature and save 
        // it to an XmlElement object. 
        XmlElement xmlDigitalSignature = sig.GetXml();
        return xmlDigitalSignature;
    }
To open the page in my client app,
string postData = String.Format("SAMLResponse={0}&APID=ap_00001&TARGET={1}", System.Web.HttpUtility.UrlEncode(builder.buildResponse("http://theWLServer/samlacs/acs",attributes)), "http://desiredURL");
webBrowser.Navigate("http://theWLServer/samlacs/acs", "_self", Encoding.UTF8.GetBytes(postData), "Content-Type: application/x-www-form-urlencoded");