Quick Fix: New-FederationTrust 426 Upgrade Required

I am working on an Exchange migration project currently, and setting up some things in a lab. As part of that I am converting what was a Modern Hybrid setup with the Hybrid Agent, to a Classic Hybrid, using connectors and what not.

I was trying to use New-FederationTrust setup a Federation trust and received the following:

Unable to access the Federation Metadata document from the federation partner. Detailed information “The remote server returned an error: (426) Upgrade Required.”