If it was in their corporate DNA to name something like the App Store the "Software Store," they would have died out in the 90's making a Windows clone.

"App" is perfectly natural for Apple, given that OS X applications (and NeXT apps before) have the extension .app