This can be caused after adding a signed certificate as this causes CAM to assume that any requests received from the service provider will be signed.
Check the STS logs for this particular error:
"CAMException : Expecting signed SAML request."
CAM is expecting the SAML request from to be signed but it isn't.
Try removing the signing certificate from the app config (use the trash icon next to the 'certificate uploaded' button for the signing certificate on the Federation Settings page) and test again.
If SSO works after removing the signed certificate contact the service provider to find out why their requests are not signed.