This is one instance where I legitimately think Apple's trademark on the term "App Store" is wholly ok.

I did two searches on the term "App Store" using Google Trends and Google Ngram Viewer.

Trends: http://www.google.com/trends?q=App+Store&ctab=0&geo=...

Ngram: http://ngrams.googlelabs.com/graph?content=app+store&yea...

Trends shows data starting from 2004. Regardless of capitalization, i.e. "app store" or "App Store", it wasn't until 2008 when the term "App Store" started entering common parlance. This coincides with Apple's introduction of its "App Store".

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.

These are only two sets of data, but at least initially it seems that Apple has a legitimate claim to a trademark on App Store.