Invalid API Key although it is valid and used for other regional APIs

I have a regional API with Api Key enabled. I've:

• created an Usage plan
• attached the Api key
• added the Api stage
• then Deployed it.
• I still get Forbidden message. (Yes, I've added the Api Key in header)

The API is created with Cloud Formation, but theUsage plan and Api are created in AWS console. I've tried to create the API in the console too, still the same error.