This also came up as one of the more dubious bits (to my mind) of Bryan Lunduke's "Why Linux Sucks" talk I wrote about a few posts back.
I don't understand why this debate won't go away and die already, because it's fundamentally silly, as anyone who's actually bothered doing any packaging knows. Why don't we have a common packaging format? Because we don't have a common distribution.
Look, there's nothing particularly important about a packaging format per se. Fedora, Mandriva, OpenSUSE, Alt Linux, PCLOS...they all use RPM, but that doesn't mean you can somehow magically use any RPM package without any problems on any of those distributions. It's the same with DEB packages - you can't magically be sure that any given DEB will work on Debian, Ubuntu and any other DEB-based distribution out there. Anyone who's looked at the OpenSUSE packaging guidelines, for instance, and compared them to the Mandriva or Fedora ones, will know that there's a huge difference between a 'good OpenSUSE package' and a 'good Mandriva / Fedora package'. Even though they're both in the same format.
Packaging, essentially, is simply providing software in a form that complies with the policies for the distribution into which you're packaging it. The package format itself plays a pretty minor role in this. If you believe that you'd suddenly be able to install anything you like on any distro if only RPM distros would adopt DEB or vice versa, heads up: you're just wrong. This is not a point of view that's up for debate, it's a simple, objective fact, which is easily verifiable just by learning a little bit about what packaging actually is, and how it's done on all the different distributions. So the fundamental tenet at the base of the 'we need a common package format' argument is simply invalid, which is enough to make the argument just a giant waste of time.
Those who make the argument need to step back and look at what it is they actually want. Usually, what some want is a world in which there's only One True Linux Distribution that everyone uses (so they don't have to worry about learning about the repository system to get packages), in which case, you might want to fill in a "I want a pony" feature request. It's not happening, it's never going to happen, get used to it. If you either want One True Distribution or bust, then I advise you to go out and get a Mac already.
What others want is something that would actually be achievable, which is a unified system to make it easier for third parties to independently provide self-contained software packages for various distributions. This is a valid desire, and something that could be done. The error is just in imagining that the way to go about this is to force all distributions to adopt a common package format, as if that'd somehow magically solve the problem (here's a hint: it wouldn't).
The most appropriate way to address this problem is fairly simple. Just write a decent distribution-independent software delivery platform. There's absolutely no reason why third parties have to deliver software to Linux users in the native package format of their distribution, and many don't. Many just provide a tarball or a binary installer, and there's nothing wrong with that. If you want to do it really snazzily, though, what you want to do is design the App Store for Linux, or Steam for Linux, or something like that. It would be perfectly possible to implement such a thing in such a way that the client (or multiple client apps! why not?) could be made available on all distributions. It could install everything to /opt or /usr/local in the filesystem layout of your choosing (go to town, people who want OS X-style hierarchies or whatever). There's no reason at all for third party application delivery to be done in the same way as first party package delivery, it's perfectly sane to have two systems.
There have already been attempts to do this sort of thing, like Autopackage. Most of them have failed, probably because they weren't very well designed or maintained. But there's nothing intrinsically wrong with the concept. Fix up one of the existing implementations or write a new one, get some buy-in from major third-party application providers for Linux (how about Google?), and then get the users on board - shouldn't be too hard.