With 500k+ apps in the store, what are the chances that a user is even going to see your app at this point? Without a ton of marketing muscle or the good graces of the kingmakers at Apple just hanging your shingle out in the App store doesn't get you anywhere.
Getting people to your app via searches on the app store can be part of your marketing, though. There are still some good niches to be found there with little serious competition.
My own personal experience is that getting in early is huge. I was in the Chrome Web Store before it officially launched and always got a lot of traffic despite barely working on the app and it being designed for Chromebooks (used a feature only available on Chromebooks) and almost no one owning those. My second app in the store got much less traffic. I had similar experience on Android (perhaps it's a Google problem). I'm trying to get into the Windows 8 market early for the same reason.
When the customer base is 20 times larger, even 10 fold competitors still keeps the market twice as attractive.
Funny how that sounds ridiculous now, no? The larger the audience the greater the potential. Successful software has always been equals parts technology and marketing.