I've had a similar error in the past. There is a default value set on one of your picklists that is invalid (default value is not a value in the picklist set). It is probably a picklist you don't even use, but because you're creating a record through the webservices it looks at every available field and uses the default value.
Go to your Admin page -> Application Customization -> Contact -> Contact Field Setup and check all the picklists (I think your error is on Indexed Picklist 4). Find the one with a default value that doesn't match an available value and fix it.