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.
At the time of the AppStore announcement by Steve Jobs, the word trademark APPSTORE and the domain APPSTORE.COM belonged to Salesforce.com
Salesforce.com dropped their APPSTORE trademark in 2008, just about the time Apple applied for APP STORE trademark. The domain APPSTORE.COM now leads to an error page within apple.com domain.
I guess we can safely assume Apple got the trademark green light and the domain from Salesforce.com, especially after—if my memory serves—Salesforce.com app was featured in one of the Steve Jobs stage announcements.
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.