Shared Connection by 2 Dataflows, one fails with Invalid Credentials

Dataflows only save the reference of the connection that you're using. Could it be that you're not using the exact same connection? Perhaps there's a discrepancy because you're using different gateways in each of those Dataflows?

have you reached out to the support team so they can run an investigation? If yes, what did they say? If not, I'd highly encourage you to reach out to the support team by creating a support ticket