I am having this same issue as well. None of the leads in the Salesforce campaign are new, and all of them have been synced to marketo already, which is apparent by their membership to the marketo program that created the SFDC campaign and synced the leads that appear in the report to the SFDC campaign itself.
This is a pretty big headache, anyone uncovered a way to resolve this error?
My guess would be that your MSI configuration is incorrect. Take a look at the appropriate setup guide and follow the instructions to reconfigure your MSI in SFDC.
Enterprise/Unlimited Edition : Configure Marketo Sales Insight in Salesforce Enterprise/Unlimited - Marketo Docs - Product Docs
Professional Edition: Configure Marketo Sales Insight in Salesforce Professional Edition - Marketo Docs - Product Docs
Failing either of those, I would open a support ticket.
I ran into this same issue. My guess is your MSI config is just fine, and you're dealing with a marketo/Salesforce latency issue like I was. The issue when I ran into this, was due to the "Change Program Status" flow step. If you have an SFDC campaign synced, Salesforce is triggering marketo to make a change to the lead/contact record in marketo's DB, which then needs to sync back to the SFDC campaign so the appropriate campaign status is set. Not an ideal situation.
One way to resolve this issue is to batch change program statuses every night instead of triggering the change alongside any other flow steps you have in place after the "campaign is requested" trigger.
Trigger Campaign
Smart List:
Campaign is Requested + Any of your other filters
Flow
Add to Engagement Program (or whatever your desired action is)
Add to (Static) List
Batch Campaign
(schedule to run at midnight every night)
Smart List
Was Added to (Static) List
Flow Step
Change program status
Worked like a charm for me. Hope this helps!