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
Apple has to show that people think "app store" means Apple's app store. How many people have to think that, and how technically inclined those people have to be, I don't know. The reaction to this story shows at least that the tech community does not think that. I don't know how trademark law deals with large rifts in public perception.
Further reading: http://en.wikipedia.org/wiki/Trademark_distinctiveness
Apple wasn't the first to have a centralized location where users could download software. If they called it the Apple Software Center I bet everyone would be calling their software centers Software Centers and we'd be having the same argument.