Universal Package Management
Just to follow up on Bob Smith's idea of using XML package description formats. It may make a lot of sense to put distribution specific issues such as prefixes into a separate file, one per distribution. That way you don't have the same information repeated in a thousand (optimistically speaking) packages. You can extend this idea to work with windowing/GUI environments as well. You could set up descriptor files for Gnome and KDE where they would indicate what it would take to update menus, etc. appropriately.
In fact, this may be a good starting point in the design of the UPM where you can clearly define all the targets and the unique charateristics of each that need to be accounted for in a successful project.
This looks like an interesting project.