Whats worse for Apple, "Kleenex" was so dominant at one point that it came close to being Genericized [1]. If the public doesn't think of a word as referring to a specific product but instead they think of "Kleenex" as a name for all soft facial tissues then in the US at least the "Kleenex" trade mark can lose its legal force.
It might be that Apple invented the term "App Store", but as long as members of the public would tend to refer to application repositories from Google or Amazon by the same term, even without Google or Amazon using it, then "App Store" isn't serving a useful purpose as a trademark and doesn't have the same legal force as a word that was in practice only specific to Apple.
I, personally, love the fact that the law around trademarks corresponds so well to their purpose - preventing consumers from being confused. This is one of the reasons I don't like the term "intellectual property", it takes three things that are very different legally and lumps them together in a way that sometimes causes people to think that the rules governing one apply to others, or that the attitudes they have towards one form should apply to all of them. Personally I'm pretty ambivalent about whether we ought to have patents and copyrights at all - but I think that trademarks are awesome and we'd be much worse off without them.
EDIT: Oops, forgot to put in the reference:
[1] http://en.wikipedia.org/wiki/Genericized_trademark