However, no one used the phrase "App Store", which is what was actually trademarked. Again, look at google trends. The "View Change Over Time" option is particularly telling.People definitely used the abbreviation "app" well before Apple launched their "App Store".
The problem with Apple's "App Store" isn't only that it's generic but also that it's descriptive.
It doesn't matter if it is the most description generic term in the world so long as it acquires secondary meaning in the public conscious, and for that Apple's marketing department deserves a gold star.