Apple filed a trademark application for the term "App Store" in 2008. Microsoft is opposing such application and has filed a motion for summary judgment with the USPTO alleging, among other things, that the term is generic. As you know, if a term or word merely describes what it is, then it is generic and will usually not be granted trademark protection. Examples of generic phrases that were turned down as marks are cited in Microsoft's brief in support of their summary judgment motion and include "The Computer Store", "Shoe Warehouse" and "Discount Auto Parts Warehouse".
Want to know what the odds are that the USPTO is apt to axe "App Store"? There should be an app for that.