bgomes,
We were able to solve this by modifying the sample code. I would suggest you add this to the sample code so others don't have to figure out something that has already been figured out.
For those who run into this issue, you can get passed this by modifying the sample code like we did.
//Create SOAP Header
$attrs = new stdClass();
$attrs->mktowsUserId = $this->accessKey;
$attrs->requestSignature = $signature;
$attrs->requestTimestamp = $timestamp;
$context = new stdClass();
$context->targetWorkspace = $workspace;
$soapHdr = array();
$soapHdr[] = new SoapHeader(self::MKTOWS_NAMESPACE, 'MktowsContextHeader', $context);
$soapHdr[] = new SoapHeader(self::MKTOWS_NAMESPACE, 'AuthenticationHeader', $attrs);
//Create Soap Client and Set Headers
$soapClient = new SoapClient($marketoSoapEndPoint ."?WSDL", $options);
$soapClient->__setSoapHeaders($soapHdr);
try {
$result = $soapClient->__soapCall('syncLead', $params, $options);
} catch(Exception $ex) {
var_dump($ex);
}