What is wrong with my SAML Response? (Office365 SSO)

Question

I have been trying to federate an Office365 domain for some time now with no luck. I have gotten to the point in which I receive a request and am able to generate a response based off that, but don't know if the response it correct. I am getting this error:

Sorry, but we're having trouble signing you in

You can't use an organizational account to sign in to this site. Please make sure that you typed the web site address correctly. If you still have trouble, you might want to contact your admin.

Here are my SAML request & responses (with sensitive info removed)

Request

<samlp:AuthnRequest
xmlns:samlp='urn:oasis:names:tc:SAML:2.0:protocol'
xmlns:saml='urn:oasis:names:tc:SAML:2.0:assertion'
ID='_1ae9c30e-8767-44e4-8221-ecd18d55e1c0'
IssueInstant='2015-03-09T20:46:12Z'
Version='2.0'
AssertionConsumerServiceIndex='0'>
 <saml:Issuer>
  urn:federation:MicrosoftOnline
 </saml:Issuer>
 <samlp:NameIDPolicy
 Format='urn:oasis:names:tc:SAML:2.0:nameid-format:persistent'/>
</samlp:AuthnRequest>

Response

<samlp:Response
Destination='https://login.microsoftonline.com/login.srf'
ID='AD5D2AFFA557338C737661EA4746DE1F5DEB0575C7'
InResponseTo='_1ae9c30e-8767-44e4-8221-ecd18d55e1c0'
IssueInstant='2015-03-09T20:46:12Z' Version='2.0'
xmlns:saml='urn:oasis:names:tc:SAML:2.0:assertion'
xmlns:samlp='urn:oasis:names:tc:SAML:2.0:protocol'>
 <saml:Issuer>
   http://self.clearlogin.com/ 
 </saml:Issuer>
 <samlp:Status>
  <samlp:StatusCode Value='urn:oasis:names:tc:SAML:2.0:status:Success'/>
 </samlp:Status>
 <saml:Assertion ID='D1B7C4F18C08B5E2A0B4811121FF8FC18E5CE2C305'
 IssueInstant='2015-03-09T20:46:12Z'
 Version='2.0'
 xmlns:saml='urn:oasis:names:tc:SAML:2.0:assertion'>
  <saml:Issuer>
    http://self.clearlogin.com/ 
  </saml:Issuer>
  <ds:Signature xmlns:ds='http://www.w3.org/2000/09/xmldsig#'>
   <ds:SignedInfo xmlns:ds='http://www.w3.org/2000/09/xmldsig#'>
    <ds:CanonicalizationMethod Algorithm='http://www.w3.org/2001/10/xml-exc-c14n#'/>
    <ds:SignatureMethod Algorithm='http://www.w3.org/2001/04/xmldsig-more#rsa-sha1'/>
    <ds:Reference URI='#D1B7C4F18C08B5E2A0B4811121FF8FC18E5CE2C305'>
     <ds:Transforms>
      <ds:Transform Algorithm='http://www.w3.org/2000/09/xmldsig#enveloped-signature'/>
      <ds:Transform Algorithm='http://www.w3.org/2001/10/xml-exc-c14n#'/>
     </ds:Transforms>
     <ds:DigestMethod Algorithm='http://www.w3.org/2001/04/xmlenc#sha1'/>
     <ds:DigestValue>
      [REDACTED]
     </ds:DigestValue>
    </ds:Reference>
   </ds:SignedInfo>
   <ds:SignatureValue>
    [REDACTED]
   </ds:SignatureValue>
   <ds:KeyInfo>
    <ds:X509Data>
     <ds:X509Certificate>
      [REDACTED]
     </ds:X509Certificate>
    </ds:X509Data>
   </ds:KeyInfo>
  </ds:Signature>
  <saml:Subject>
   <saml:NameID
   Format='urn:oasis:names:tc:SAML:2.0:nameid-format:persistent'
   NameQualifier='http://self.clearlogin.com'
   SPNameQualifier='urn:federation:MicrosoftOnline'>
    ABCDEG1234567890 
   </saml:NameID>
   <saml:SubjectConfirmation
   Method='urn:oasis:names:tc:SAML:2.0:cm:bearer'>
    <saml:SubjectConfirmationData
    InResponseTo='_1ae9c30e-8767-44e4-8221-ecd18d55e1c0'
    NotOnOrAfter='2015-03-09T21:06:12Z'
    Recipient='https://login.microsoftonline.com/login.srf'/>
   </saml:SubjectConfirmation>
  </saml:Subject>
  <saml:Conditions
  NotBefore='2015-03-09T20:46:12Z'
  NotOnOrAfter='2015-03-09T21:06:12Z'>
   <saml:AudienceRestriction>
    <saml:Audience>
      urn:federation:MicrosoftOnline 
    </saml:Audience>
   </saml:AudienceRestriction>
  </saml:Conditions>
  <saml:AuthnStatement AuthnInstant='2015-03-09T20:46:12Z'>
   <saml:AuthnContext>
    <saml:AuthnContextClassRef>
      urn:oasis:names:tc:SAML:2.0:ac:classes:Password 
    </saml:AuthnContextClassRef>
   </saml:AuthnContext>
  </saml:AuthnStatement>
  <saml:AttributeStatement>
   <saml:Attribute Name='IDPEmail'>
    <saml:AttributeValue xsi:type='xs:string'
    xmlns:xs='http://www.w3.org/2001/XMLSchema'
    xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance'>
     [REDACTED]
    </saml:AttributeValue>
   </saml:Attribute>
  </saml:AttributeStatement>
 </saml:Assertion>
</samlp:Response>

idP

We are using a third party idP (ourselves) for creating the SAML response. We are NOT using ADFS.

Set-MsolDomainAuthentication

Import-Module MSOnline
$idpSub = Read-Host 'Please enter the idP subdomain on clearlogin.com: '
$passiveLogin = "https://"+idpSub+".clearlogin-stage.com/apps/office365/login"
$logout = "https://"+$idpSub+".clearlogin-stage.com/apps/logout"
$issuer = "https://"+$idpSub+".clearlogin-stage.com/"
$certPath = C:\Users\MyUser\Desktop
$cert = New-Object
  System.Security.Cryptography.X509Certificates.X509Certificate2($certPath)
$certData = [system.convert]::tobase64string($cert.rawdata)
$msdomain = Read-Host 'Please enter your Office365 domain.'
Set-MsolDomainAuthentication
  -Authentication Federated
  -DomainName $msdomain
  -FederationBrandName $msdomain
  -IssuerUri $issuer
  -LogOffUri $logout
  -PassiveLogOnUri $passiveLogin
  -SigningCertificate $certData
  -PreferredAuthenticationProtocol Samlp

EDIT 1:

Added some more info and my Set-MsolDomainAuthentication command.

Answer 1

The issues seemed to lay in a few places. The cert had the wrong issuer encoded, and the digest values were wrong.