I've fixed my issue.
The problem was that my machine was registered with SwitchToInt.bat
from the XBoxLIVE SDK, in order to work with other features.
PNs apparently only work in Prod environments, so when testing PNs you need to call SwitchToProd.bat in your XBoxLIVE SDK folder.
I have not found this mentioned anywhere on the docs, the samples or the forums.
If anyone knows where this is mentioned, please let me know.
I hope this helps fix your problem.