So we had a new GPO push on some servers which broke our Solarwinds connection to our SQL server.
It turns out it was, the Network Security options setting in the GPO for "Configure encryption types allowed for Kerberos" We're only allowing AES128/256_HMCA_SHA1, and future encryption types. If I also check the RC4_HMAC_MD5 it fixes all my problems.
What I'm not sure is where exactly this setting would be to change this.