Maybe you didn't use the TI-83+, which has an "Apps" button on it, and was designed in 1999.
And though I agree that Apple has put a lot of effort into its app store, I feel like saying that they should have sole access to the term is comparable to AOL suing anyone who uses "instant messenger" to refer to something other than AIM.
Edit: See also: MS Office, MS Word, MS Security Essentials, and arguably MS Internet Explorer and Windows Explorer (I browse the internet and manage/browse files--there's not much literal "exploring" going on)
You never 'open a window', or 'close a window', or 'change a window'? You might be younger than me (I'm 30) but I've been doing that since having an Atari ST in the last 80s.
Same reason you can buy "linux" laundry detergent.
I heard the term "killer app" at least 10 years ago. "App" is not only generic but it's been out there for a long time.
Edit: Here's the earliest I can find the word in print. It's from 2002. http://www.fastcompany.com/magazine/55/love.html
"1985 Info World (Nexis) 9 Dec. 41 At first look, the user sees only one new menu (‘apps’ for applications) at the top of the screen."
Because of its NeXTSTEP heritage, Mac OS X uses a lot of NeXTSTEP lingo, like 'app', 'dock' and 'plist'.
' And, of course: make the apps available with just one click. '
Date is Jan 2007, before the iPhone was ever released.
http://liquidat.wordpress.com/2007/01/24/clickn-run-for-fedo...
The point is that 'apps' have entered into common usage to refer to applications on all mobile platforms. 'App' is a generic term, that isn't attached to a brand. So, if you agree that 'Store' is also generic, then 'App Store' can't really be anything but.
All of the words in the English language are gone for naming purposes. If you want to alter the laws to prevent protection of novel phrases then you doom us all to a future of Xobni, Loopt, Wufoo, Weebly, Buxfer, Zenter, Zecter, Fuzzwich, Fliggo, Voxli, Nambii, Olark, Mertado, Movity, and other companies drawn as Scrabble™ hands. (Ok, you can't draw Fuzzwich.) Names that don't function as names because you can't say them to someone and have that person later use them to identify the entity because they can't spell it, don't know what it means, and will forget it before they need it.
Allowing generic words to be trademarked too easily causes problems. International Business Machines seems like a fine name right up until there are many multi-nationals making business machines. At that point IBM starts to sounds more like a descriptive (It's an IBM, it's got English and German on the keys...)
Selectric on the other hand, seems like a name the public benefits by protecting.