Did anyone really use 'App Store' in everyday language before the one on the iPhone? Someone says that they used it internally in their company, but I'd suggest that this was the exception - it was not an everyday term.
I'm not being pro-Apple here, but their case is actually stronger than the case for 'Windows'. Maybe they're both bad, but Apple's is still stronger. I certainly referred to 'X Windows' (however incorrect that may be!) before I ever saw Microsoft Windows, so is just 'Windows' a valid trademark?
So people may or may not think that 'app store' is something they said before the iPhone, but the majority of people definitely didn't use it. Also, while I guess it's more likely that people might combine 'app' with the word 'store' in the US, that would never be a natural thing to say in the rest of the world. For example, you'd say 'shop' in the UK, not 'store'. Perhaps 'App Store' is actually far less generic in most of the world than 'Windows' is? Apple should perhaps try to register the trademark in the UK - they'd get far less grief.