Additional features, settings, or issues not covered by specific Microsoft Teams categories
As it turns out our issue was between our reverse proxy and with later versions of Android being stricter on requirements by the looks of things.
Look for a "Require SNI hostname" setting in any load balancers or reverse proxies to your Federation services and try adjusting that if necessary. This was the fix to our issue.