Cannot authenticate REST API calls using right credentials (API Token). Getting 401 Unauthorized

Summary

Using correct email address and API Token (or password) is not working when authenticating REST API calls.

Notes

The bug in on the Identity side, and it will equally affect Jira, Confluence and Stride. This usually happens when using managed accounts (using SSO or Google Sync to log-in) and it is caused by some change that didn't propagate correctly, like, e.g:

1. A user change's their email
2. SAML user changes email at the IdP
3. User has their email updated by an org admin

Steps to Reproduce

1. Log into the instance and open an issue (e.g. ISSUE-123)
2. From the browser, call the REST endpoint to get the issue information and see that you get the correct response (https://INSTANCE/rest/api/latest/issue/ISSUE-123)
3. Generate an API Token and use it to authenticate a REST API call against the same endpoint (https://INSTANCE/rest/api/latest/issue/ISSUE-123)

Expected Results

You get the same REST response than in step 2

Actual Results

You get error 401 Unauthorized instead.

Workaround

It is usually enough to log into id.atlassian.com with email address and password (better if from an incognito/anonymous window) to have the changes propagated.