After installing a custom built SharePoint App on a new Sharepoint tenant, I was unable to get the App-Only calls working.

First I ensured the apps had permissions Allow the add-in to make app-only calls to sharepoint enabled.

Once I determined that to be true, I inspected the calls using fiddler, and I noticed the return was:

{"error":"invalid_request","error_description":"Token type is not allowed."}

Yet again, Office365 had changed the default settings to new SharePoint sites. The problem was the property DisableCustomAppAuthentication was enabled.

To disable this property I used the following powershell commands

Connect-SPOService -Url https://mysite-admin.sharepoint.com/
set-spotenant -DisableCustomAppAuthentication $false

And Voila, the app was able to make App-Only calls.

I hope this helps save you time!