Do you have a special use of SFDC, such as Contacts Only?
From your description, I can't really tell what's going on. Marketo views everything as a "Lead" but will have a field SFDC Type = Contact, Lead, User which you can use to distinguish those people.
Converted leads should be a Contact now, so that part doesn't make sense to me.
In which direction are you expecting the sync? Are these records created in SFDC first, or Marketo?