I figured out the reason: StreamWriter was adding a zero-width Byte Order Mark to the start of the XML before base64 encoding, and Okta couldn't interpret the resulting XML auth request. (Thanks, James.)
I have the same problem. SAML client - mod_auth_mellon. I am able to catch saml request with saml tracer, but it does not give me idea what is going wrong. Also there is nothing useful in the logs, available via partner okta dashboard. What else can be done to debug this issue?