Apple has been very inconsistent on their use of it though. Originally you just searched for apps in iTunes Store. Then I believe it changed to iTunes App Store. And now they have a Mac App Store. the other point is that apple refers to them as 'apps' in a generic sense and not something like 'App Store applications'
such that the public comes to identify the relevant term with one vendor and not as a primarily descriptive term, then that item is said to acquire "secondary meaning.
It is not clear that the public identifies "app" as something from Apple only.
I've definitely had a few encounters where it seems there's a good chance the average, non-technical user, considers 'app' to refer explicitly to iOS applications. I remember somebody wanting to work on a project asking if I had written any 'apps', I assumed he meant applications and I listed off some of the more interesting projects on various platforms. He seemed utterly confused that I was talking about things that were not running on an iphone.
It's a biased selection but, Google's Page Rank certainly says that the public tends to "link" the term 'App Store' to 'Apple' in a pretty consistant manner
On the other hand, half of the "related searches" on that page are "nokia app store", "android app store", "samsung app store", etc., which are not the official names of any of those brands. Its possible that the public uses more formal names when linking but less formal names when searching.
The "there's an App for that" campaign by Apple has definitely helped cement that as a possibility. I'm pretty sure when folks use / mimic / parody that phrase, they're always referring to Apple's use, not some generic "app".
As long as they've not been SO successful, that consumers now consider "App Store" to be "The thing you get stuff for your phone from" where phone could be WinMo or Android or Symbian.
I don't know if that should matter. If Facebook spends billions promoting it's brand and then sues people making books with faces who called it, lets say Staunch's face book, I don't see how they deserve to win.