[SalesForce] Rest API: The Requested Resource does not Exist

I am trying to get a Salesforce REST API Integeration to work and struggling quite a bit.

I've got a successful authentication via OAuth that returns an access_token.

I'm using that access token as "Authorization: Bearer $access_token" header when trying to make further requests. However, whatever my request looks like, I get

[
  {
    "errorCode": "NOT_FOUND",
    "message": "The requested resource does not exist"
  }
]

as response.

Details:

I request the header via CURL:

curl  -XPOST  "https://test.salesforce.com/services/oauth2/token" \
  --data-urlencode "grant_type=password" \
  --data-urlencode "username=$EMAIL" \
  --data-urlencode "password=$PASSWORD$SECURITY_TOKEN" \
  --data-urlencode "client_secret=$CLIENT_SECRET" \
  --data-urlencode "client_id=$CLIENT_ID"

the response i am getting looks like this:

{
  "access_token": "TOKEN_VALUE",
  "instance_url": "https://xxx.my.salesforce.com",
  "id": "https://test.salesforce.com/id/xxx/xxx",
  "token_type": "Bearer",
  "issued_at": "1558087410145",
  "signature": "xxx"
}

Then, using that access token to craft a request (same result for any request – tried many different ones):

curl "https://xxx.my.salesforce.com/services/data/45.0/sobjects/Lead/listviews"  \
  -H 'Authorization: Bearer TOKEN_VALUE'

Response

[
  {
    "errorCode": "NOT_FOUND",
    "message": "The requested resource does not exist"
  }
]

The Connected App has "full" permission, and the username/password credentials i log in with has access to the data I am querying via
lightning web. I also verified that API Version 45 corresponds to the salesforce version used.

Du you have any suggestions, on what I am doing wrong?