Well, this worked, but I am kind of amazed you have to do it this way.
First, I used the Data Loader to download all contacts as a CSV file.
I then opened the file in Excel, and added the XLS of names emails as a second sheet which I called "campaign".
Then I re-arranged the contact list to have the email address first, and the contact ID second. Then I sorted the contact list by email address.
Moving to the SC sheet, I added a column “ContactID” and put this formula in the first cell:
=VLOOKUP(D2,contacts.csv!A:B,2,FALSE)
Then I copied that formula to every row. I then sorted the "campaign" sheet by the ContactID field, and copied the valid ContactID rows to a third sheet called “addtocampaign.csv” and copied the #N/A names, companies, and emails into a sheet called “campaignleads”. I exported both those sheets as CSVs. I imported the first into the campaign as “Contacts” and the second as “Leads” and it worked!