Updating contacts with different Company name through import

I am trying to do a update csv import process to update existing contacts and tie them to different company records.  Reason for this is the current data is tied to Other Name companies instead of Leads.  I need to update the contacts so they're tied to the Lead records (which I'm importing separately first) and then delete the Other Name records.

I successfully imported the Lead records.  Now I'm trying to update the contacts through the import process with the correct Company record, but it's failing every time.  And if I do an add/update, it creates a duplicate contact, which I obviously don't want.