WNS push notification fails with Unauthorized: "AppId is not allowed to post Webpush notifications to WNS"

Question

We have been using WNS for years via VAPID authentication to send push notifications to our side-loaded Windows app. This still works to this day.

However, recently we needed to change the code-signing certificate that is used for this app, and this results in the Package ID of the app changing, as well as the SID. The VAPID public/private key pair has not changed (and should not need to, either, as it is not linked to the way the app binaries themselves are code-signed).

When our application server attempts to send push notifications to the app with the new code-signing certificate, the WNS returns an error response of Unauthorized. Looking deeper at the headers in the response we can see the following:

"AppId is not allowed to post Webpush notifications to WNS"

Though it was many years ago when we first set this up, I do not recall there being any additional steps about registering the App ID. Am I mistaken?

How do we get our new App ID to be allowed to send push notifications?

These are simply "alternate channel" notifications going to our UWP app. There is nothing fancy about them. And they aren't "Webpush" in the sense that they are going to a web browser - that isn't the case.