One thing that might help is a kind of meta-package format: a file which, when downloaded, is run by a client native to the given distribution. The client then goes to the software repositories for the program maker and obtains all the right packages to make that program run on that particular machine. The folks at BitRock have something vaguely like this, where you can package a given open source application in such a way that it will run natively across multiple platforms, Linux included.
Another major way this is being addressed is through the Linux Standards Base. In order to be LSB-compliant, a Linux distribution must either use Red Hat's RPM natively or have support for RPM. Given that the most popular distribution out there right now is Ubuntu -- a Debian-derived distribution that doesn't have much support for RPM -- there's been criticism that the LSB is "too Red Hat-centric" for this to work.
Any given Linux distribution is an agglomeration of components from thousands of different programmers, projects, and architectural initiatives. To that end, there's little or no centralized configuration: everything in the system is controlled through a welter of files, and there's no guarantee that the syntax of any one configuration file will apply to any other.
The problem is not as pronounced if you limit your exposure to only a few files and follow their internal formatting, but that's not a sustainable solution. A lot of this is due to retention of compatibility with legacy UNIX applications. One of the worst offenders has been sendmail, whose configuration files traditionally reached new lows of complexity and obscurity.
There needs to be a consistent -- and whenever possible, self-documenting -- configuration system throughout, from the kernel to userland tools and user applications. Aside from making it easier for the user (and the programmer) to deal with, it might also simplify central administration issues.
Dictating something like that by fiat is probably impossible; a better approach would be to popularize the use of a toolset that makes it easy for applications to have a unified configuration approach. The GNOME project's Gconf is a good example of this sort of thing; even if the current iteration is intended for user preferences rather than system-wide configuration options, it's still a good real-world example for how to create such a thing.
Kernel Application Binary Interfaces
If there is one complaint that comes up more often than any other about developing for Linux, it is the way the kernel application binary interfaces are a moving target.
The Linux kernel has been designed from the perspective that what's inside the kernel can change, but what's available to user applications through the ABIs cannot and must not break. The problem is not only philosophical, but also practical: the sheer breadth of kernel interfaces means it's entirely possible for something to break (or "regress") in a way that might not even show up in a fairly rigorous code review.
To that end, when something does break, it creates two problems: it means the exact source of the problem is sometimes a matter of argument (i.e., is this a kernel issue or a user-application issue?), and time and effort is lost in the process of fixing it.
There are a few ways to work around the problem in the short term. One of the most immediate and promising workarounds for certain projects is FUSE -- short for "Filesystem in Userspace" -- which allows file systems, normally the domain of the kernel, to be set up in the same space where user applications run. In the long run, though, Linux needs an ABI set that's not only stable but capable of handling long-term growth without becoming a rat's nest of potential compatibility issues.