I get this error message. Other people refer to this error message as well, where it turns out their App has not been published yet. Ofcourse I understand Windows will give me 404 when the app hasn't been published yet. Only problem is: MSDN App HUB states that it has already been published, but I still keep getting this error. It has been well over the 2 hour - margin in which MSDN says they will publish it. Also, I have the deep link, something that I shouldn't have, had they not published the app, I reckon? Any idead on what may cause this error?
If usually takes longer than 2 hours for the app to be available after being published. I would suggest waiting for 24 hours until starting to worry. As long as your app is not visible in the Marketplace search, it should be ok.