Zoho CRM API Error AUTHENTICATION_FAILURE "Authentication failed"

Zoho CRM API Error AUTHENTICATION_FAILURE "Authentication failed"

I am trying to integrate a web app with the Zoho CRM API. Following the instructions in the API docs, I did the following steps:

1) Went to Zoho Developer console (https://accounts.zoho.com/developerconsole) to register my client application. 
It is a "Self client" app, so I just put a dummy Client Domain("testing"), and dummy Authorized redirect URIs("http://www.testing.com").

2) Again from the Zoho Developer Console, I clicked on the "..." options button for the client I registered and selected "Self client".
In the menu that appears I entered the scope "ZohoCRM.modules.ALL,ZohoCRM.settings.ALL", selected 10 minutes for expiry, and clicked "View Code".

3) Leaving the View Code window open, I copied the code and sent a Postman request like this:
The response I got was:
{
    "access_token": "1000.4cb45da9219eXXXXXXXXXXXXXXXXXXb380e4761ab5dd7795f67e",
    "refresh_token": "1000.70d5acd7986XXXXXXXXXXXXXXXX7e864253c84b177b338cbb51b13",
    "api_domain": "https://www.zohoapis.com",
    "token_type": "Bearer",
    "expires_in": 3600
}

4) When I try to send any api requests, GET or POST, Leads or Contacts or Accounts, where my request looks something like:
Authorization: Zoho-oauthtoken 1000.4cb45da9219eXXXXXXXXXXXXXXXXXXb380e4761ab5dd7795f67e

I always get the same response:
{
    "code": "AUTHENTICATION_FAILURE",
    "details": {},
    "message": "Authentication failed",
    "status": "error"
}

If I change any part of the token so it is wrong, or if I try to change the request url to www.zohoapis.eu or www.zohoapis.in instead of www.zohoapis.com I get the following response instead:
{
    "code": "INVALID_TOKEN",
    "details": {},
    "message": "invalid oauth token",
    "status": "error"
}

5) When I send a request to refresh the token like so:
I get back a new access token but trying to make api calls with the new token gives the same AUTHENTICATION_FAILURE response
{
    "access_token": "1000.42a2d57506XXXXXXXXXXXXXXXXXXXXXXXdc33fbb5121028",
    "api_domain": "https://www.zohoapis.com",
    "token_type": "Bearer",
    "expires_in": 3600
}

Please help, I'm not sure what is going wrong.