The GetUserInfo operation of the UserGroup.asmx web service contains the SID that can be parsed out if you can utilize that.
<?xml version="1.0"?>
<xml>
<GetUserInfo xmlns="http://schemas.microsoft.com/sharepoint/soap/directory/"><User IsDomainGroup="False" IsSiteAdmin="False" Notes="" Email="myemail@mydomain.com" LoginName="domain\alexandere" Name="Pirate, Eric" Sid="S-1-5-21-2072177302-1958620249-3085007271-234531" ID="1"/>
</GetUserInfo>
</xml>
Meaning that after a user is selected from the people picker, you can use that value to call the web service to retrieve the SID.