As a developer and CS major, promotion is a thing I personally despise. It keeps me away from creating. And how can everyone in the world not be as excited about my brand new essential product as I think they should be? Unfortunately, no one knows about it until you tell them. And until you tell them, they won't download it. And in the business world, where number of downloads and revenue is the measure of success, you have failed. But you want to succeed, and therefore you promote.
Every new mobile app developer has ran into this problem. The first big realization for me was that you need to dedicate the same amount of effort to promote an app, if not more, as you need to develop the app. Now, I am not saying a good app won't go a long way towards making it easier to promote, but without quality promotion even the best app succeeding is left to chance.
Promoting takes a long term commitment and needs to start well before the app is complete.
Having developed and released an app with 50000+ users and recently released a small app https://play.google.com/store/apps/details?id=com.xconcepts.findme Find Me as an experiment, I still find it hard to promote simply because it is in a different cateogry of apps. It requires getting to know people in different communities and realizing where your new target audience is.
Take a look at http://samuelfine.com/iphone_lessons_learned.html this article by Samuel Fine
Hustle. Hard. is his end point. Although comical, the main point does echo what needs to be done. You need to promote your app to every single person you can and keep promoting it to them to help them understand why they want and need it.
Check out http://onstartups.com/tabid/3339/bid/80121/How-To-Get-Media-Coverage-For-Your-Startup-A-Complete-Guide.aspx this article by https://twitter.com/leowid Leo Widrich. Although he is talking about start-up promotion, I think every single point in the article applies to mobile app promotion.
Hope this helps, and good luck promoting!