I think the app store has become much more about marketing now when you are entering with a new app. Most of the built in discovery tools are focused on apps with an existing reputation. Given the volume of apps this makes sense, and helps ensure that users are shown quality apps, however it also places a barrier to entry to newcomers until they can build a reputation that allows this virtuous cycle to take hold.

I would be interested in hearing from any app developers who have managed to break through this cycle recently and the marketing techniques they used.