@jokerseven unfortunately I think that's the way things are going now. Unless you spend a load of money or are extremely lucky, you're going to struggle. You need to think of it as a long game and constantly keep pushing, releasing updates and focus on driving up organic traffic (e.g. App Store Ratings and Optimisation)
For example, we wrote to nearly 200 people (app review sites, bloggers, etc) and have had not one review. Despite that, literally everyone who plays the game absolutely loves it, and our App Store ratings show that too. I caught two people playing it in the local gym earlier this week, that's how addictive it is!
I'd also say what little money we spent on marketing hasn't really made any difference, so I agree with the others here - if you're going to spend, you'll need to spend a lot.