So, how I fixed it (in my mythical alsheppard.com domain).
- In the AD FS mmc tool, on the right is the "Edit Federation Service Properties" and change the FS name and identifier.
- Add the new DNS name sts.alsheppard.com to point to the same IP address as the fs.alsheppard.com
- Update the certificate that it uses. Powershell and run "Update-ADFSCertificate". This will generate the new token-decrypting certificate and token-signing certificate that you can see in the MMC (under AD FS -> Service -> Certificates). The fs.alsheppard.com certificate is still the primary.
- In the gui, notice that you can't change the primary and secondary around yet. In the powershell, run "set-ADFSProperties -AutoCertificateRollover $false".
- In the gui again, change the new sts.alsheppard.com to be the primary and delete the old fs.alsheppard.com certificates in both sections.
- In powershell, run "set-ADFSProperties -AutoCertificateRollover $true"
- In ADUC, change the SPN value on the ADFS farm service account from "host/fs.alsheppard.com" to "host/sts.alsheppard.com"
- In the Powershell again, type "get-ADFSSslCertificate" and this should show three certificates, two for the fs.alsheppard.com hostname and one for localhost. Copy the CertificateHash and use it here "set-ADFSSslCertificate -thumbprint <CertificateHash>. Run the get-ADFSslCertificate again and there should be 5 certificates now, one for localhost, two for the old name and two for the new name. This must be done on each server in the farm.
- In the mmc, change the Device Registration Service identifier too (AD FS -> Trust Relationships -> Relying Party Trusts).
- Restart the ADFS service.
In hindsight, deleting the farm, wiping the farm server and restarting from scratch would have been about as easy.
Edited 20150908 to change the set-ADFSProperties certificate rollover, thanks anonymous commenter!