SSO issue with “AADSTS50008: Unable to verify token signature.”

A client trying to log in to the Office 365 portal gets the following error message:

AADSTS50008: Unable to verify token signature. The signing key identifier does not match any valid registered keys.

After replacing the ADFS 3.0 Service Communication certificate with a new one (instead of the expired certificate), the issue appeared. The steps were completed according to a useful blog article

The new certificate is valid, but clients still cannot log in to the portal. What’s the solution? Microsoft recommends running the following command from PowerShell on the ADFS server, but only if you want to manually renew the token‑signing certificates — which I think is a good idea in our case:

Update-MSOLFederatedDomain -DomainName [verified domain]

The same problem is described here.