In the end I opened a support ticket with the Azure team and over the course of a few hours we tracked down the issue to a missing certificate for the remote desktop add on to the web role.
The certificate thumbprint given by the team was one that wasn't present in the portal nor was it ever part of my solution. Unfortunately, this detail was only given by the team and isn't displayed when the deployment failed.
However, the solution was to remove the remote desktop add on, redeploy the service and re-enable remote desktop.
We have now been able to deploy using an HTTPS endpoint with no further issues.