Probably the best thing to do Askok is post your SAML Response to the forum. I've just worked through the same error and it was down to a few things:
NameID must be present and must be the Google Apps username of the user logging in, i.e.
<saml:Subject>
<saml:NameID Format="urn:oasis:names:tc:SAML:1.1:nameid-format:unspecified">YOUR_USERNAME</saml:NameID>
<saml:SubjectConfirmation Method="urn:oasis:names:tc:SAML:2.0:cm:bearer">
<saml:SubjectConfirmationData Address="some.ip.address" InResponseTo="cicgpdbkndjjopbdeeknjhgkmpinklimjmhkhamk" NotOnOrAfter="2011-03-22T14:15:21Z" Recipient="
https://www.google.com/a/YOUR_DOMAIN/acs"/>
</saml:SubjectConfirmation>
</saml:Subject>
RelayState MUST be sent back as-is - don't URL decode or encode it. Just pass it back. You only seem to get the "broken robot" page if you make a mess of RelayState though, which is a different error.
Make sure there are no empty attributes in the response. There should be no attributes at all. Google Apps only needs the Subject with a valid NameID. If you include an empty attribute statement you will see that error.
What you also need to know is Google Apps SSO will try to force passive authentication at your IdP. If you don't support this you need to return the appropriate SAML Response and Google will send a new SAML Request with passive authentication turned off
Not sure if this applies to ADFS but I suspect it probably uses LDAP entities on the backend so make sure you're not passing back a DN instead of a CN in the NameID
Below is the two step SAML exchange between the Guanxi IdP and Google Apps SSO that I know works:
<samlp:Response ID="gxesh27f5ub8drsb3jlaoav0fpq6" Version="2.0" Destination="
https://www.google.com/a/YOUR_DOMAIN/acs" IssueInstant="2011-03-22T13:14:48Z" InResponseTo="iaiihpcbgjhoegnfdjdlboalkcdhgkdhjmckinii" xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol" xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion">
<saml:Issuer Format="urn:oasis:names:tc:SAML:2.0:nameid-format:entity">YOUR_ENTITY_ID</saml:Issuer>
<ds:Signature xmlns:ds="
http://www.w3.org/2000/09/xmldsig#">
<ds:SignedInfo>
<ds:CanonicalizationMethod Algorithm="
http://www.w3.org/2001/10/xml-exc-c14n#"/>
<ds:SignatureMethod Algorithm="
http://www.w3.org/2000/09/xmldsig#rsa-sha1"/>
<ds:Reference URI="#gxesh27f5ub8drsb3jlaoav0fpq6">
<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#">code ds kind rw saml samlp typens #default</ds:Transform>
</ds:Transforms>
<ds:DigestMethod Algorithm="
http://www.w3.org/2000/09/xmldsig#sha1"/>
<ds:DigestValue> ... </ds:DigestValue>
</ds:Reference>
</ds:SignedInfo>
<ds:SignatureValue> ... </ds:SignatureValue>
<ds:KeyInfo>
<ds:X509Data>
<ds:X509Certificate> ... </ds:X509Certificate>
</ds:X509Data>
<ds:KeyValue>
<ds:RSAKeyValue>
<ds:Modulus> ... </ds:Modulus>
<ds:Exponent> ... </ds:Exponent>
</ds:RSAKeyValue>
</ds:KeyValue>
</ds:KeyInfo>
</ds:Signature>
<samlp:Status>
<samlp:StatusCode Value="urn:oasis:names:tc:SAML:2.0:status:Responder">
<samlp:StatusCode Value="urn:oasis:names:tc:SAML:2.0:status:NoPassive"/>
</samlp:StatusCode>
</samlp:Status>
</samlp:Response>
<samlp:Response ID="gxn7kg3j35r0of19371um4gkho5u" Version="2.0" Destination="
https://www.google.com/a/YOUR_DOMAIN/acs" IssueInstant="2011-03-22T13:15:21Z" InResponseTo="cicgpdbkndjjopbdeeknjhgkmpinklimjmhkhamk" xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol" xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion">
<saml:Issuer Format="urn:oasis:names:tc:SAML:2.0:nameid-format:entity">YOUR_ENTITY_ID</saml:Issuer>
<ds:Signature xmlns:ds="
http://www.w3.org/2000/09/xmldsig#">
<ds:SignedInfo>
<ds:CanonicalizationMethod Algorithm="
http://www.w3.org/2001/10/xml-exc-c14n#"/>
<ds:SignatureMethod Algorithm="
http://www.w3.org/2000/09/xmldsig#rsa-sha1"/>
<ds:Reference URI="#gxn7kg3j35r0of19371um4gkho5u">
<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#">code ds kind rw saml samlp typens #default</ds:Transform>
</ds:Transforms>
<ds:DigestMethod Algorithm="
http://www.w3.org/2000/09/xmldsig#sha1"/>
<ds:DigestValue> ... </ds:DigestValue>
</ds:Reference>
</ds:SignedInfo>
<ds:SignatureValue> ... </ds:SignatureValue>
<ds:KeyInfo>
<ds:X509Data>
<ds:X509Certificate> ... </ds:X509Certificate>
</ds:X509Data>
<ds:KeyValue>
<ds:RSAKeyValue>
<ds:Modulus> ... </ds:Modulus>
<ds:Exponent> ... </ds:Exponent>
</ds:RSAKeyValue>
</ds:KeyValue>
</ds:KeyInfo>
</ds:Signature>
<samlp:Status>
<samlp:StatusCode Value="urn:oasis:names:tc:SAML:2.0:status:Success"/>
</samlp:Status>
<saml:Assertion ID="gxmmgedtb0v8ghmhnio5j2n4mmle" IssueInstant="2011-03-22T13:15:21Z" Version="2.0">
<saml:Issuer Format="urn:oasis:names:tc:SAML:2.0:nameid-format:entity">YOUR_ENTITY_ID</saml:Issuer>
<saml:Subject>
<saml:NameID Format="urn:oasis:names:tc:SAML:1.1:nameid-format:unspecified">YOUR_GOOGLE_USERNAME</saml:NameID>
<saml:SubjectConfirmation Method="urn:oasis:names:tc:SAML:2.0:cm:bearer">
<saml:SubjectConfirmationData Address="ip.address.of.login" InResponseTo="cicgpdbkndjjopbdeeknjhgkmpinklimjmhkhamk" NotOnOrAfter="2011-03-22T14:15:21Z" Recipient="
https://www.google.com/a/YOUR_DOMAIN/acs"/>
</saml:SubjectConfirmation>
</saml:Subject>
<saml:Conditions NotBefore="2011-03-22T13:15:21Z" NotOnOrAfter="2011-03-22T14:15:21Z">
<saml:AudienceRestriction>
<saml:Audience>
google.com/a/YOUR_DOMAIN</saml:Audience>
</saml:AudienceRestriction>
</saml:Conditions>
<saml:AuthnStatement AuthnInstant="2011-03-22T13:15:21.865Z" SessionIndex="860e1c78883a682e07697c494b0ff1641847b128ec28cc8b597fb">
<saml:SubjectLocality Address="ip.address.of.login"/>
<saml:AuthnContext>
<saml:AuthnContextClassRef>urn:oasis:names:tc:SAML:2.0:ac:classes:PasswordProtectedTransport</saml:AuthnContextClassRef>
</saml:AuthnContext>
</saml:AuthnStatement>
</saml:Assertion>
</samlp:Response>