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.

    Access your files securely from anywhere

        Zoho Developer Community




                                  Zoho Desk Resources

                                  • Desk Community Learning Series


                                  • Digest


                                  • Functions


                                  • Meetups


                                  • Kbase


                                  • Resources


                                  • Glossary


                                  • Desk Marketplace


                                  • MVP Corner


                                  • Word of the Day



                                      Zoho Marketing Automation


                                              Manage your brands on social media



                                                    Zoho TeamInbox Resources

                                                      Zoho DataPrep Resources



                                                        Zoho CRM Plus Resources

                                                          Zoho Books Resources


                                                            Zoho Subscriptions Resources

                                                              Zoho Projects Resources


                                                                Zoho Sprints Resources


                                                                  Qntrl Resources


                                                                    Zoho Creator Resources



                                                                        Zoho Campaigns Resources


                                                                          Zoho CRM Resources

                                                                          • CRM Community Learning Series

                                                                            CRM Community Learning Series


                                                                          • Kaizen

                                                                            Kaizen

                                                                          • Functions

                                                                            Functions

                                                                          • Meetups

                                                                            Meetups

                                                                          • Kbase

                                                                            Kbase

                                                                          • Resources

                                                                            Resources

                                                                          • Digest

                                                                            Digest

                                                                          • CRM Marketplace

                                                                            CRM Marketplace

                                                                          • MVP Corner

                                                                            MVP Corner





                                                                              Design. Discuss. Deliver.

                                                                              Create visually engaging stories with Zoho Show.

                                                                              Get Started Now