Parse.com Push Subscription does not work on Windows Phone 8.1

I'm trying to get Parse.com Push notifications running on Windows Phone 8.1 (from this Tutorial).

It seems that the initialization works:

ParseClient.Initialize("my app-id", "my key");

But when I'm trying to subscribe to the broadcast channel, the following exception gets thrown:

await ParsePush.SubscribeAsync("");

The notification platform is unable to connect to the cloud notification service. (Exception from HRESULT: 0x803E011B)

It is an Universal App (C#) and I have enabled "Toast capable" within the Package.appxmanifest file.

I have also authenticated the Windows Store App by adding the Package Security Identifier and the Client Secret to the Parse.com Windows Push Credentials settings (following this tutorial). But this does not solve the problem..

Any solutions regarding this problem?

Funny, it worked after I installed the beta-app from the market (and deleted it afterwards again).

The next deployment of the production-app via Visual Studio worked for me (no exception anymore) - The device is now connected to the Parse service :)