Apply replacements for unknown packages early.

Now we change uid of unknown packages just prior to fetching. That
should improve user's experiences when performing a complex upgrade.