> Incidentally, you *can* change package names without having the UUID. 
> People do it in Debian by having a transition period where 
> both packages are present and the new one "provides" the other
> one.  It's more than trivial, but it's still not that big of a deal.
> The nice thing is that all the tools can just immediately display
> and modify package names, instead of having to look up in some
> global table what all the UUID's mean.

Err, excuse me, but why can't you have both? Seems to me that something like
a 'named object' might contain both, name and uuid (what a concept, eh? ;)
Then, you can stick all the logic you want into this guy and live on happily
ever after.

Cheers,
  - Andreas