Interesting. So you think "Gas Station" is generic. Which I would agree with. On the other hand, I have never heard a gas station being called "GasStore", so if one of the fuel companies called there gas stations "GasStore" then they should be able to get a trademark on it. So if Exxon called their gas stations "GasStore" and five years from now that word is in everyone's mind (which is the idea), then BP would of course want to use the name as well and everyone would claim it is generic.
Same with AppStore. Nobody used the word AppStore before Apple did. The words App and Store were used, just as Gas and Store are being used, but nobody used the combination AppStore.