Issue Description
Recently I came across an issue, where immediately after adding the site collection app catalog and uploading the app package, I am getting the below issue.
"Cannot enable the site collection app catalog feature in this site collection because it has not been approved by the tenant admin"
The package upload failed. The message says 'The app catalog cannot be activated'.
The first pre-requisite is to have the account that is having SharePoint admin rights must be Site Collection admin of the site collection where the app catalog needs to be activated.
Even after that, you are getting this message, you may have to wait for 15 to 20 minutes and then upload the app package again.
Fix
In my case, I have to wait for 15 to 20 minutes. The error message is a little misleading, but a 15-minute wait worked for me.