The error is somewhat misleading and it took me a while to figure out what was going on, but the issue is that when you're replacing the default "App Script managed" project, if you're not the owner of that project, then you can't delete it and set a new project; so this error message isn't referring to the newly created cloud project, which does exist and which you are the owner of, it's referring to the automatically created apps script managed project.
What this means is that you can only set a new project when you open the script editor on a spreadsheet you're the owner of (I guess).
For me I first realised this when I went to the "File" menu in the script editor to choose "Delete Project" and saw that it didn't exist, even though I was an editor of the original spreadsheet. It wasn't until I was logged in as the owner of that spreadsheet that I could see "Delete project".
Even when I deleted the project, and then went and opened the script editor first from the other file owner, I still didn't have the Delete Project option, and I also still couldn't set the project number.
What I ended up doing was:
Assume A is the original owner of the script, and B is an editor of the script, and also the owner of the new cloud platform project.
1) From the cloud platform project, logged in as B, add A as an owner of the project
2) From the Script editor logged in as A, set the cloud platform project to the project number
3) Configure the oauth consent screen from A
Now the project number has been replaced, the Apps Script managed project is deleted, and account B owns the cloud platform project even though they are not the owner of the script.