The story is as follows:
I have taken over looking after a PowerApps instance, and starting off, there were four provisioned PowerApps environments. One of the environments needs to be scrapped and re-created, so I deleted this environment. I then tried to create a new environment and have been presented with the following error:

This is unexpected, because when there were four environments, I could see that they had all been created by the same user as indicated by the "CREATED BY" column, and the user used to create the environments is the same user that I'm using to create a new environment.
I have also confirmed that from a licensing point of view, I should be allowed to create Production environments, in particular, I've confirmed that the "Dynamics 365 Customer Engagement Plan Enterprise Edition" covers production PowerApps facilities.

What could be the problem?