After MS support pointed us in the direction of TLS, adding the following line fixed the error for us:
System.Net.ServicePointManager.SecurityProtocol = System.Net.SecurityProtocolType.Tls12;
Still don't understand why after years of working fine today was the day it needed to be changed.
Edit: While the above definitely fixed the error, the line we ended up using was:
System.Net.ServicePointManager.SecurityProtocol |= System.Net.SecurityProtocolType.Tls12;