Comment 15 for bug 188579

I've investigated, by looking at apt's internals and it seems like apt just always installs the first available package to satisfy the depends (ordered by priority, but that's not important here).
I've filed a bug in Debian about it, but I suspect that we have to revert back to using "Recommends" instead of "Depends".
I'm still interested in any feedback/ideas, of course.