Device not receiving C# Windows Push Notifications because channel url incompatible

After many hours of trial, I still fail to send push notifications to my app. This is what I did so far:

• Activate the service at https://appdev.microsoft.com

• Got the SID, lets call it ms-app://s-1-23-4-12345678901-...-12345678901

• Received the client secret, lets call it 12Lwq7526OqNY8iN-aLkwds23451345

• In my app I implented the following at some point (simplified):

  PushNotificationChannel channel = null;
  channel = await PushNotificationChannelManager.CreatePushNotificationChannelForApplicationAsync();
  System.Diagnostics.Debug.WriteLine(channel.Uri);
  

• This prints an url of that kind:

  https://db3.notify.windows.com/?token=AgY7AABrfRCVgRV%2ba4DwoDjC2omrnOVwCkdhCrrzlJi6UpIwHzcig6%2fG5xZfnDqU0%2fXoE848ddiqyTaTlSSltp2Dn9Z3qaPsMAyh7kS%2bmlis1%2bwoh%2b%2b4DsAK1yeV1d9G1rUIuFs%3s
  

• I added correct package name, publisher display name and publisher ID to my Package.appxmanifest file

• So I thought I was ready for testing push notifications. Using my own implementation of push sharp, fiddler output is the following:

  Request:

  POST https://db3.notify.windows.com/?token=AgY7AABrfRCVgRV%2ba4DwoDjC2omrnOVwCkdhCrrzlJi6UpIwHzcig6%2fG5xZfnDqU0%2fXoE848ddiqyTaTlSSltp2Dn9Z3qaPsMAyh7kS%2bmlis1%2bwoh%2b%2b4DsAK1yeV1d9G1rUIuFs%3s HTTP/1.1
  X-WNS-Type: wns/toast
  Authorization: Bearer EgAC4AA1hAZAQMAklDAAEgAAAUe8/AGsK8a/yk78/WEDQf+KUld/nYIvJ51OIoCPgAfwqbl0oo1sPDLhd9ChiO/iLFVzwlTPE3trp9oTkJxNXi0yUrf+FKjRciq7Utek9B/4dxH9lFNy0R5iwdMS0xNS0yLTIyNDgyMDE1NzEtMjczODcxMjkyMy0yMzM3MbsS59ZuQmXCIAFoOiAAAAAAAgzMOTB7OuFIezrhS60gEAAoANS45LjYuMTBiPoPMh3Nj5MAEOp0RhrcMUx6D50AtDuzWE1AAAAAABeAG1zLWiwcDovL3MtTk2Nzk3LTEzOTYwNDkxODYtMjEyODYwMTQ3MS04MDg1MDg2ODUtMzY3NjQyNTk3OQA=
  Content-Type: text/xml
  Host: db3.notify.windows.com
  Content-Length: 138
  
  <toast>
    <visual>
      <binding template="ToastText01">
        <text id="1">This is a test</text>
      </binding>
    </visual>
  </toast>
  

  Answer

  HTTP/1.1 403 Forbidden
  Content-Length: 0
  X-WNS-ERROR-DESCRIPTION: Channel URL incompatible with caller app
  X-WNS-MSG-ID: 5FC550364E079585
  X-WNS-DEBUG-TRACE: DB3WNS4011533
  Date: Mon, 23 Dec 2013 23:58:22 GMT
  

• I found this post Channel URL incompatible with caller app so far which was not really helping

I get the same error using the web service of http://31daysofwindows8.com/push. What can I do here? What could have gone wrong? Please note that this app has not been published yet to the store and I am testing on my local Windows 8.1 installation.