I have been getting the same errors. After opening a ticket with Marketo, this is what I found, provided your permissions are appropriately set up:
1. Detailed error messages related to the background campaign sync is not shown in the Activity Log for a lead. So, if you get an error, you have to contact Marketo Support to find out the exact error message.
2. Most of the time, the failure is because the lead was converted in Salesforce. Marketo is trying to add a lead to a campaign, but that lead has been converted in Salesforce since the last sync, and Salesforce will not allow any actions on converted leads. Strangely enough, somehow the related Contact does make it into the campaign.
3. To rule out permissions being the problem, you will still need to contact Marketo Support to get the underlying error message. The full message might look something like this:
Failed: INSUFFICIENT_ACCESS_ON_CROSS_REFERENCE_ENTITY: insufficient access rights on cross-reference id SFDC Campaign id: 701C0000000iaPIIAA, Lead/Contact Id: 00Q8000000bjv25EAJ
If you aren't a Salesforce administrator, you can give the full failure message to her, and she can help you troubleshoot if it is permissions by logging in as the user who does Marketo syncing and attempting to add the lead/contact to the campaign.
It would be great if Marketo could log these in the activity log of the lead. But, of all the things to fix, this is a minor one.