It's a pity, Linux on desktop could have gone way further on market share and popularity. Now, they are doing just a copy (wait for Apple to demand).
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.)
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>
dpkg -i <some-random-deb-you-downloaded>
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.
it's about dev friendlyness.
in case your didn't know, your favorite appstore also has dependencies. the difference is that they bundle all libraries per OS version. Linux distros bundle per lib version (and thus per package).
but that's all up to the dev to fix, not to the user.