Not so much - they have to have different names. I couldn't have a package named, e.g., linux-kernel and install version 3.4, 3.5, etc, instead I have to install linux-kernel-$version, each of which is a different package.
a) The requisites for most package managers out there are not that different (i.e. it's the same problem).
b) We have the problem so beaten down that we should be able to properly define the solution boundary.
Is the deb solution suboptimal? Probably. It's not relevant to the main point being argued.
But if a package manager is anything, it's an implementation. It's not a theoretical concept, it's a tool that a user has to smooth the process of their work. Both could just install and configure packages by hand but it's the implementation that makes a package manager useful (for one being able to run multiple versions and for another being explicitly discouraged from multiple versions). Dismissing implementation details in a tool that is designed for implementation is missing the point.
This is actually a good example of the good definition of the problem space. All corner cases have been dug up. It's not a priori obvious that an operating system needs multiple versions of a package, but in some cases it does. And the package manager supports it.