REST API Key not recognised despite being correct

Another thought, just to verify. Are you creating a private app or public one?