I'm not sure whether Apple should be able to patent the name "App Store," but it certainly does raise a question of what a brand is. Surely, before the iPhone, people off the street would be confused by the term "App Store". Yet, after the iPhone (iOS >= 2), you could pull someone off the street and they would say something like "oh yeah, that's where you buy apps for the iPhone." So I don't think it's reasonable to dispute that Apple popularized the term "App Store," essentially invented it in the public eye. That said, it is a store to buy applications, which Apple did not invent, even in the public eye.
There are lots of terms / brands which encode the product in the name in a fairly obvious manner. Should American Airlines be allowed to use that as their brand? Or is it too generic, given that there are many airlines based in America? Should a brand like KitchenAid be able to patent their name? Or is it too obvious of a name, given that the company produces aids in the kitchen? Should uniqlo be able to patent the term heattech, or is it obvious given that it's a technology designed to preserve heat? It's a very difficult distinction to make, and I'm not sure which side is right.