I'd contend that discovery is a problem faced only by app creators, not app consumers. This makes solving the "problem" difficult, since it's hard to convince the consumer to venture out into non-app store venues to look for hidden gems.
If I do want a particular application, I search Google first than the app store. Most probably some one has already gone through the pains of finding an app and has talked about it online.
So discovery problem exists for app consumers as well. And there in lies a startup idea in app discovery but I wonder how Apple/Google would allow that.
After 10 pages of that, I gave up.
Searching the App Store or the Play is a painful experience whether you're just browsing around to find something interesting or if you're looking for something that does a specific thing. The categorization isn't fine-grained enough and the "curators" will pretty much let anything thru without showing any signs of quality or originality.
The desktop software market still suffers from this a little bit, but enough time has passed that some standards for quality have emerged from the general consciousness. You release a desktop app, there are some gold standards to compare to.
If anything, the app market is going to be incredibly painful for quite some time.
From a user perspective, the goal of discovery is to find the best apps that match my interests. This goal is hard to reach because of a poor user experience paired with inefficiencies in search and the download process.
It's this culmination of factors that makes app discovery a headache.
disclaimer: i know these guys
I know that the specific app isn't your point - it's more about the general question of discoverability, but I rarely find too much difficulty finding at least one reasonable example of the kind of app I'm searchig for.