Facepalm.
Spotify has every right to use that "shelf space" to advertise their product. They're trying to sell a service and turn a profit on that service. Due to the makeup of the mobile landscape, their only choice if they want their product to succeed is to have it on the App Store. There's no sideloading. There's no alternative shop. And unfortunately, due to Apple's 30% cut, they are unable to make the same kind of profit on one sale that Apple does with their similar service.
Now, I know that some of you will say, "Just don't sell on the App Store, then." Unfortunately, it's not that cut-and-dry. Mobile is huge, and there are few people that will take the time to get on a computer just so they can purchase an app subscription. If the option is not there on their phone, they just won't bother. Not to mention, removing themselves from one of the most popular mobile platforms is a very risky move--there's absolutely no guarantee that people would switch to Android for just one app.
Now, here's the thing that I don't understand--Spotify is trying to sell access to their service, not the app, so why should that be governed by Apple? I could understand if they were selling the actual app, but they are not.
Also, for those talking about Apple's 30% cut going towards overhead, what the hell is the $99 they charge for the Developer Program put towards, if not that?