i have tested with CRM 2015 vanilla version below is XML using SOAP UI but i am facing same error.
Microsoft.Crm.ObjectModel.PicklistAttributeValidator.Validate
<?xml version="1.0" encoding="utf-8"?>
<soapenv:Envelope
xmlns:soapenv="schemas.xmlsoap.org/.../"
xmlns:ser="schemas.microsoft.com/.../Services"
xmlns:con="schemas.microsoft.com/.../Contracts"
xmlns:sys="schemas.datacontract.org/.../System.Collections.Generic"
xmlns:i="www.w3.org/.../XMLSchema-instance"
xmlns:c="www.w3.org/.../XMLSchema">
<soapenv:Body>
<ser:Create>
<ser:entity>
<con:Attributes>
<!-- STRING DATATYPE-->
<con:KeyValuePairOfstringanyType>
<sys:key>name</sys:key>
<sys:value i:type="c:string">DM Testing 3</sys:value>
</con:KeyValuePairOfstringanyType>
<!-- LOOKUP DATATYPE-->
<con:KeyValuePairOfstringanyType>
<sys:key>parentaccountid</sys:key>
<sys:value i:type="con:EntityReference">
<con:Id>B0A8CF24-1F9B-E511-80DF-00155DCBB69B</con:Id>
<con:LogicalName>account</con:LogicalName>
<con:Name i:nil="true"/>
</sys:value>
</con:KeyValuePairOfstringanyType>
<!-- DATETIME DATATYPE-->
<con:KeyValuePairOfstringanyType>
<sys:key>estimatedclosedate</sys:key>
<sys:value i:type="c:dateTime">2015-12-12T09:56:00</sys:value>
</con:KeyValuePairOfstringanyType>
<!-- MONEY (CURRENCY) DATATYPE-->
<con:KeyValuePairOfstringanyType>
<sys:key>discountamount</sys:key>
<sys:value i:type="con:Money">
<con:value>1000</con:value>
</sys:value>
</con:KeyValuePairOfstringanyType>
<!-- OPTIONSET DATATYPE-->
<con:KeyValuePairOfstringanyType>
<sys:key>new_customertype</sys:key>
<sys:value i:type="con:OptionSetValue">
<con:value>100000000</con:value>
</sys:value>
</con:KeyValuePairOfstringanyType>
<!-- TWO OPTIONS SET DATATYPE-->
<!-- <con:KeyValuePairOfstringanyType>
<sys:key>cbg_cancellableswap</sys:key>
<sys:value i:type="c:boolean">false</sys:value>
</con:KeyValuePairOfstringanyType>-->
</con:Attributes>
<con:LogicalName>opportunity</con:LogicalName>
</ser:entity>
</ser:Create>
</soapenv:Body>
</soapenv:Envelope>