You know, I don't really know anyone who called them "apps" before the iPhone came out. Even now, I know many people (myself included) who make distinctions between programs/software/applications and APPS. It may be shorthand for applications, but especially with the initial push of APPS, how they were smaller, generally less full-featured, portable applications, is it not possible that is was intentional to call the APPS to imply all this as opposed to just using lazy shorthand?
And just because other people call other company's digital storefronts and offerings "App Store(s)" doesn't mean that's what they are. They are called that due to the resounding and overwhelming success of THE App Store.
The ONLY reason I disagree with Apple getting that TM is that it is a frivolous TM. Immitation is the sincerest form of flattery and all.