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.
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.