If navigating the store were a little less like pulling teeth, a few extra applications wouldn't cause so many problems.
Break down the categories a bit more, make the view all button obvious and make it show everything, not just the first 200. Make the search a little more advanced.
I find everything about the itunes store difficult to get at what i want. Even if i know the exact application but not it's name I struggle to find it