OK so there were a few issues here, firstly the Exchange Back End website had lost it's certificate association which stopped all comms with the Exchange server including powershell:

And so we could not change anything.
We had to repair the association with the site in the IIS manager bindings:



Once the certificate was reinstated, we ran IISReset on the server and then we regained access to Exchange PowerShell
We could then re-associate all of the services with the correct certificate using:
Enable-ExchangeCertificate -Thumbprint [Thumbprint] -Services POP,IMAP,IIS,SMTP
All we had to do after that was to re-associate the relationship with our edge-transport server as we use one, but otherwise you should be done. 🖐