Microsoft is arguing that Apple cannot trademark the term app store because it is a generic term.
"An 'app store' is an 'app store'," Russell Pangborn, Microsoft's associate general counsel, said, according to the BBC. "Like 'shoe store' or 'toy store', it is a generic term that is commonly used by companies, governments and individuals that offer apps."
A commenter at Hacker News begs to differ:
Ngram data shows no usage of "App Store" or "app store" from the time of 1800 to 2008. I was suspicious of this, but using the terms "app,store" separately produced lots of data points. My tentative hypothesis is that Ngram is using data that existed before the App Store went public and thus will not show up in Ngram.
I'm no trademark expert, but the basic idea, as Wikipedia defines it, is distinctiveness: A trademark may be eligible for registration, or registrable, if amongst other things it performs the essential trademark function, and has distinctive character. Registrability can be understood as a continuum, with "inherently distinctive" marks at one end, "generic" and "descriptive" marks with no distinctive character at the other end, and "suggestive" and "arbitrary" marks lying between these two points.
First, I used BYU's Corpus of Contemporary American English and found an instance in 2009 of 'app store" being used to describe Zune's product: Oh, the Zune has an app store, all right. As of today, there are exactly nine programs in the Zune App Store.
A quick google search reveals that it commonly gets applied to non-Apple related products as well: Yep, Amazon Launching Their Own App Store For Android Too.
While it may be the case that Apple introduced the term in 2008, it seems to have expanded to generic use in less than a year and now gets used at least semi-regularly for non-Apple products. I'm not an Apple user myself and my own reading of app store is definitely generic. It does not distinctly mean Apple's product at all, to me. I have no clue if a court would agree.