If 'App Store' trademark is generic, so is Microsoft's 'Windows,' Apple argues (appleinsider.com)

With that logic, Apple is not selling app stores either.

This is the point that I think will make the difference. It's not like Microsoft has trademarked 'Operating System'; they're using a generic word in a specific context. Likewise for Blackberry, Android, Twitter, etc.