I strongly disagree that the iOS App Store should be treated as an "internet service" rather than a part of the device. The iOS App Store only comes on iOS devices, it comes on all iOS devices, and it is the only way to access a crucial feature of the device. It is, for all meaningful purposes, part of the iPhone in the same way iOS is.
It would be a bit like Microsoft saying "explorer.exe? Policy A only covers the OS, and that is clearly not part of Windows! - so therefore you are covered by Policy B". While Apple may be legally in the right, I strongly believe they are morally in the wrong and have betrayed the trust their users put in them to safeguard their privacy.
I believe that a casual user of the iPhone would take a look at Apple's iPhone privacy policy and expect that to apply to the iOS App Store as well, as for all intents and purposes that is a part of the iPhone.