Prior art is a patent thing, not a trademark thing. It's not because no one used "Shoe Store" before in a commercial setting to talk about their store that sells shoes that you can trademark "Shoe Store". App Stores are a dime a dozen and are a category of stores, stores that happen to sell apps as abbreviated for applications.
Anyway, seeing how the USPTO initially denied Apple and only came to the objection phase after Apple badgered them, I don't see how they'll get the trademark granted after this high profile objection to it. It seems the deck is stacked against them and rightly so. "Mac App Store", "iTunes App Store", go for it, but I can't really approve of them trying to trademark "App Store", just like I wouldn't approve of 7-eleven trademarking and renaming their stores "Convenience Store".
I wasn't arguing about prior art. My argument was this: after all Xerox became synonymous with the whole class of product, so did Kleenex and Plexiglass. And each company did have a fight over trademarks because of that. However, they won because 1) they all launched marketing campaigns to re-promote the generic title that existed before them and 2) it was after all associated with their product and their product only before the product became such a huge success that the name of the product became generic.
I do agree that simply coining a phrase does not make you owner of it. My argument is whether the "App Store" first became a thing associated only with Apple and which then became a success and people began to use it generically (ala Xerox) or if Apple took a generic name and is now trying to associate only to them and their product. That's the relevant argument.
However, the USTPO did authorize their claim, this is an appeal of that decision. I'm not sure it is fair to claim that Apple any more badgered them by appealing than Microsoft is by appealing.