Make sure you are syncing over the status and that the assignment rule in Salesforce is set based on this. For example, in Marketo your sync campaign is set with:
Smartlist trigger - Lead is Created, Source type is not Salesforce
Flow: Change Data Value of Status to "New Lead" (or whatever you want, we use New Lead b/c all leads sync to Salesforce from the beginning)
In Salesforce create a Markto rule under your Lead Assignment Rules. It should look like this:
Order=1
Criteria= Lead:Lead Status equals New Lead
This should create the lead in Salesforce. Of course you want to work in your assignment rules of who gets assigned new leads unless you are the default and get assigned all new leads.
Hope this helps.