Solving "PackageUriForbidden" Authorization Failure in Azure Cloud Service ES Deployment

To resolve the "PackageUriForbidden" error when deploying an Azure Cloud Service (Extended Support), follow these detailed steps

I am trying to redeploy an Azure Cloud Service (classic) to an "extended support" one since the former is being deprecated. Following this guide and the prerequisites I have created a virtual network and new storage account. I set up a bunch of permissions and the Connectivity Check for my storage account indicates no problems. However when I try to create and deploy a new Cloud Service (Extended Support) using my (updated) .cscfg, .csdef and .cspkg files I get this error:

Error:AuthorizationFailure, message:This request is not authorized to perform this operation. (Code: PackageUriForbidden)

I've tried setting the container and blob access to public for the deploy files, I have added Network Contributor and Storage Blob Data Contributor to both the subscription and the cloud storage resources for my user account. What am I missing?

How to resolve the above issue ?

To resolve the "PackageUriForbidden" error when deploying an Azure Cloud Service (Extended Support), follow these detailed steps: