I think people are confusing the difference between a generic term, and brand name. Apple haven't trademarked the use of App Store as a generic term, it's a important part of the Apple brand.
Windows is generic word, but it's also a popular brand name. If another company set up show selling software under the name Windows. Microsoft would sue because that new company is using the Windows brand to it's own advantage. Microsoft won't sue a double glazing company because they sell double glazing windows because there is no cause for confusion.
Whilst app store may have become a generic term that people do now use commonly. It doesn't change the fact that the App Store is an existing brand, and a trademarked one at that. Apple won't sue someone for using the term generally, but if they're using it to sell their own software market, they have every right too because there is opportunity for consumer confusion and again, Amazon could be seen to be abusing the success of the Apple App Store to springboard their own.
There are countless brand names built around generic words, names. Coke is trademarked by Coca Cola, and can only be used by them as a brand but how many people will generically refer to a lesser branded cola product as Coke? you may refer to it as coke, but it's label and branding won't mention the word!
