Hi Graham,
From this article we know that there are several ways can be used to create a Common Data Service database. Which way are you using?
The article link is:
https://powerapps.microsoft.com/en-us/tutorials/create-database/
I use the way “Create a database in the Entities pane of powerapps.com”. Firstly, I create an Environment, then create the database. But when I create the database, I get the same error with you:

After getting this error, I try another way “Create a database in the admin center”. I get another error which shown as below:

Seems that I already have 2 databases, it has reached the limit. The fact is that I already have 2 databases, so I am not able to create a database.
Please check how many databases have you created, please also try to create a database in the admin center to see if you would get the same error with me.
Best regards,
Mabel Mao