I didn't have quite as bad an experience submitting my app (http://codecube.net/2012/09/introducing-viewer-for-khan-acad...) to the w8 store. But it did fail the first time and I was quite annoyed at the reason. It failed for requirement 4.1.1:

"If your app has the technical ability to transmit any user's personal information, you must maintain a privacy policy. You must provide access to your privacy policy in the Description page of your app, as well as in the app’s settings as displayed in the Windows Settings charm."

Now, my app is open source, and doesn't collect any user information whatsoever. And not only that, but the app's meta data during submission has an optional field for a privacy policy URL.

So I just ginned up a quick privacy policy that says we don't capture any personal info (http://codecube.net/khanacademy/privacy/), added it to the settings charm, and resubmitted. It passed.

But it was annoying.