Bolding is mine.
How would you feel if someone had trademarked "Movie Theater" or "Dance Hall"
Just because they were first doesn't mean they have the "right" to "own" it.
Again - I think Apple was good to TRY and if they succeed - more power to them. But I don't think it's really trademark-able.
If they wanted to trademark AppStore - that would be different.
The last is even debatable since AppStore and App Store are the same in conversation and trademarks don't just stipulate that you have to be exactly the thing your trademarking. A breach of trademark just have to be close enough that a reasonable person could confuse branding for another and result in a loos of business for the company with the trademark. As such App Store and AppStore are largely equivalent.
However, you are right that coining a term does not signify ownership unless you are the one create a brand around that term which others do not use and cannot refer to the general class.