Mali and Egypt are in no way alike.
Well, no one's going to be fully satisfied when you deal in civilization/colony names.
Krikkitone's solution has the advantage of probably being a lot easier to implement. I personally don't like locking the same colony civs/leaders into coming from the same civs every game.
My solution has the advantage of adding a little more flavor to the game (and not tying the same civs to putting the same leaders in charge of the same colonies every game -- in fact, since the name of the civilization is completely new, both leaders and civilizations could be randomized; for instance, the English colony of Canada could actually have Tokugawa as leader, while using the civ benefits of, say, Rome.) Of course, this would take a little more development time, but I think it'd be worth it (especially since I'm not the one who has to do it.

)
In any event, whatever solution is chosen, I think the consensus is that a solution IS required that, at a minimum (a) eliminates the duplicate leader problem, (b) eliminates the duplicate civ problem (where a foreign civ tells you to stop trading with the Americans, but there's three American civs, two of which are colonies,) and (c) allows the player a chance to re-name the colonial civ at the time of creation.