It would help to have a bit of trademark law primer to understand the issue here. A "trademark" is a "mark" (a name or graphic, etc.) that is used in commerce to identify the source of a product. There are five types of marks: fanciful, arbitrary, suggestive, descriptive, and generic.
A fanciful mark is one that has no prior meaning, and thus usually is a made-up word. (e.g. Kodak, Verizon, Slashdot)
An arbitrary mark is a word with existing meaning but is arbitrarily connected to the product which it labels. So therefore "Apple" is arbitrary when it is used to describe a manufacturer of computers, but not when used to describe an apple farmer.
A suggestive mark is one that *suggests* a quality or feature of the product, but does not describe it directly. Courts usually describe such a mark as requiring a "step of imagination" to get from the mark to the product. Examples include "Coppertone" for suntanning lotion, or "Playboy," or "Home Depot," or "SourceForge."
A descriptive mark is one that directly describes a quality or feature of the product: "International Business Machines," "American Telephone and Telegraph"
Finally, generic marks are those that merely describe the general class of which the product is a member: "corn flakes," "raisin bran," etc.
Fanciful, arbitrary and suggestive marks are considered "inherently distinctive." They can be registered as-is (subject to minor restrictions, like being used in commerce), and immediately grant their owner the right to prevent others from using that mark in commerce. (To be clear, it does not prevent other people from using it for non-commerce purposes, nor does it prevent "nominative" use, where the other party is using it to describe the trademark owner's actual product -- as in, "our service is better than Verizon's")
On the opposite extreme, generic marks are never protected. The middle ground is for descriptive marks, which have to have acquired "secondary meaning" before they can be protected. This means that, despite its lack of inherent distinctiveness, the public must have come to associate that mark with the source. For example, when someone sees "IBM" on a computer they have a very specific idea of the company that produced that product.
The question, it would seem, is whether "App Store" is descriptive or generic, and if descriptive, has it acquired secondary meaning? It seems to me that it is *not* suggestive -- one does not need a leap of imagination to realize that an "App Store" is a store where one buys apps. Personally, I'm inclined to say that it is generic -- an "App Store" is a class of stores, of which "Apple App Store" is one member (the latter is protected as an arbitrary mark, btw).
This contrasts with "Windows," which is either suggestive or descriptive with acquired secondary meaning. Arguably, one needs imagination to jump from the mark "Windows" to "an operating system with graphical user interface." One could claim that "Windows" merely describes one aspect of that operating system, namely that it displays windows, but the counter argument would be that the term "window" itself, as used for a collection of pixels on the screen that displays the output of a computer program, is itself a suggestive term (i.e., it bears little resemblance to the traditional definition of Windows). Furthermore, even if descriptive, "Windows" has acquired secondary meaning, as it is universally understood to refer to the Microsoft product. Whoever first coined that term might have had the right to prevent Microsoft's use at some point, assuming that they used it in commerce, but that right has lapsed by failure to maintain it.
Anyways, that's what they taught me in IP class in law school. Hopefully that is helpful.