First of all "Windows" itself doesn't mean an OS. You can argue that OSes have generic GUI windows, but Microsoft is not suing to prevent Gnome from calling itself a window manager with application windows. "Windows" is a trademark for an operating system.

>So then, possibly an "app store" doesn't just mean a store on Main St, that happens to have applications on its shelves, but a novel concept worthy of a trademark?

Well, store doesn't really mean only physical stores right? There are a bunch of online shops calling themselves stores from the 90s.