"App Store" (capital A, capital S, taken together as a unit) is only popular today because Apple popularized it and transformed the mobile software landscape. I don't think Apple should be victims of their own success, with enough companies trying to ride on their popularity wave that the trademark becomes so commonly used that it's invalidated.
"app" may be generic, "store" may be generic, but that's not what's trademarked here. Apple hasn't trademarked "app" to speak of "Apple applications", but only the term "App Store" in the business of online stores.
Narrowed down like that, App Store wasn't used before the iPhone for online stores, and Apple was fairly granted the trademark in my opinion. Judges shouldn't overrule fair play for some reason like "oh, now so many have started using Apple's trademark, that we can just as well invalidate it!" Ridiculous.