Not sure if your situation is the same as ours was Scott, but we had the same problem. After reverse engineering the process, we discovered that we had a form that was not requiring First Name and Last Name - two fields that SFDC requires for sync. So whenever those types of incomplete leads went through the workflow, the sync bombed and generated that error. Take a look at the membership of that campaign, and more specifically the leadsthat were NOT synced/added to SFDC, and it should be relatively easy to identify the similarities....
Good luck