Hi Dan,
You weren't the same guy who described a similar problem with XmlDSig interop on the microsoft.public.dotnet.security newsgroup on 5/4/2009, are you (he posted as "tom").
I saw that post but did not respond because I don't really consider myself an xmldsig expert at this level of detail.
My understsanding is that it tends to have interop problems due to misinterpretations of the required canonicalization of the input XML before the signature is computed. As you can imagine, different canonicalizations due to white space handling would produce different input binary data and thus different hashes and signatures.
My other understanding is that the interop problems are partially the result of the actual spec not being tight enough leading to different interpretations. That tends to lead to finger pointing as to who is right and who isn't. In some cases, the toolkits themselves give you too much flexibility and require you to perform these steps yourself which leads to "operator error". :)
What you really need is someone who can look at the actual dsig stuff and tell you what is wrong, but that guy isn't me.
I will say that plenty of the cross platform toolkits for SAML and WS-Fed (which uses SAML at the XMLDsig level) DO interop just fine, so someone must have libraries that work but I don't know what they are. I have no idea if OpenSSL is faulty here or just the usage of it.
Good luck finding an answer.