The biggest challenge seems to be that there is a very limited amount of information available. Marketing text, category, and maybe rating (Though I think you have to violate Apple's ToS and scrape to get that.) Apple already offers free-text search, but I think few use it.
Most approaches so far have gone for trying to create a social network around app discovery, which seems like a lost cause to me (how many people are going to join such a network?) I could be wrong though...