When I first submitted my app to the Windows Store it failed certification due to the Windows 8 app certification requirement 4.1: http://msdn.microsoft.com/en-us/library/windows/apps/hh694083.aspx
At the time, the 4.1 requirement wasn't entirely clear to me but, after some digging on the internet, I was able determine what was needed.
The good news about the certification requirement documentation is that it appears to be improved over time because section 4.1 is now a bit more clear as to what is needed.The reason why my app failed certification was because any app that makes a connection to the internet, which our app does, can result in some of your user's personal information making it onto the internet (e.g. the IP address could be used to determine their location).
Since every app is different, the common recommendation is to go through the Windows Store apps looking at the various privacy policies to come up with one that best fits your app's functionality.
(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)