The App Store is user-friendly. Do you want that program? Download it! No worries of dependencies. So it doesn't matter if it's proprietary or not. It's a matter of user experience and wanting to make it easy for non-techies. They have improved a lot but it's sad they weren't the first to make that change.
apt-get install <something-in-repository-or-ppa-you-added>
will bring down all the dependencies needed. That's the reason they package stuff against release numbers, so the dependencies are all consistent. dpkg -i <some-random-deb-you-downloaded>
may give dependency errors.But a quick apt-get -f install after I get those errors sorts it out.
Random downloading of debs from Web sites could lead to a situation where a different version of a dependency is needed. "foo needs libnaff-ubuntu345 but libnaff-ubuntu345 is not going to be installed" type errors result.
if you used synaptic to install programs, it highlighted dependencies in the GUI, but that was really just irrelevant information - there was no user interaction required other than clicking the install button on the thing you wanted.
The process is much better than on OSX. Think about how no app installs Growl automatically.
I think you answered your own question. Package management (together with distribution policies to make those packages work together) has solved this problem for Linux already, for all software packageable by distributions, which includes pretty much everything needed to make a usable system. An "app store" just makes it easier to get one-off non-redistributable proprietary apps, which Linux historically hasn't cared much about until other OSes started to, at which point a few Linux distributions started wondering whether catering to proprietary app developers would make the system more popular. (Personally, I'd argue that apps follow platform popularity, not the other way around.)