Thanks Erik, here is my xml body (it doesn't work with any lead selector i try, but if i take out the lead selector it works)
<ns1:Body>
<ns0:paramsGetMultipleLeads>
<leadSelector xsi:type="ns0:LeadKeySelector">
<keyType>EMAIL</keyType>
<keyValues>
<stringItem>someemail@company.com</stringItem>
</keyValues>
</leadSelector>
<batchSize>100</batchSize>
<includeAttributes>
<stringItem>Title</stringItem>
</includeAttributes>
</ns0:paramsGetMultipleLeads>
</ns1:Body>