ok, what fixed it in my case was creating a new Live app, rather than test. They must have something wrong with the test environment not working properly. Sandbox api worked fine, however, not what I needed.
I get the same error, with rest api key, sending a simple python request:
BASE_URL = “https ://api.company-information.service.gov.uk” #space added so it doesnt complain about url