Application store. Software store. If you want to use the word store. But there is no need to. App Market is clear enough, isn't it? A market is a friendly, open place where you buy a variety of things at good prices, not walled in and regulated like a store. I'd say "Welcome to App Market, the place where you find all the software you need".
I'm not sure anyone would use the terms 'Application' or 'Software' in relation to phone apps. If someone asked me where they could buy software for their phone, I'd be genuinely confused as to what they meant.
I guess the question I'm asking is: does there need to be a generic phrase to describe app stores, which can't be trademarked? If you were to say "App Store and (say) App Market are app stores", what else would you call them if not app store? And if someone trademarked "Application Store", does that mean that name can't be used? (And am I right in thinking that if Apple wins, the term "app store" can't be used descriptively?)
Ok, that's 4 questions not 1!