Use of Named Credentials seem to be tied to External Data Source

The error occurs if your named credential is configured to use per-user authentication but the currently logged in user that is trying to use the named credential (or their administrator) has not added their credentials to the Authentication Settings for External Systems section (located under My Settings) for that named credential.

The error message mentions external data sources because under the hood, the features share a lot of the same code. But it is confusing, and a bug.