Need advice for moving records from one org to another

I need to move a lot of records from one org to another.  Normally, I export the records from the source org with Data Loader, then insert them into the target org with Data Loader.  This involves starting with the Users, then the Acounts, but you have to use Excel/Xlookup to update the User ID's on the Accounts with the new ID's.  Then I insert the Contacts, after I use Excel/Xlookup to update the User ID's and Account ID's.  This takes a lot of time, and there's a decent chance of making an error.  I found a SF video explaining how to use an External ID field to upsert records.  I created a new External ID Account field called "Old_AccountID__c" and added that field to the Account file and copied the old Account ID to the column.  I created a new External ID Contact field called "Old_AccountID__c" and added that field to the Contact file.  Then I copied the old Account ID to that field.  I tried upserting the Contact file with Data Loader and using that field as the external ID reference, but it didn't work, I just got errors.   

Is there a way to do what I'm trying with Data Loader?  Am I missing a step? 

Thanks