Below are two ways to achieve this.

First is the UpdateACompany method that shows how to do it using the update method. The second is UpdateACompanyRecord, this shows how to do it with the updaterecord method.

The code examples are in C#.

'binding' is the name of the CRM webservice object.
'multifield' is the custom multiselect field 'comp_multifield'.

Using the Update method

private static void UpdateACompany()
{
ewarebase[] companyList = new ewarebase[1]; //can add any number of companies to update
company aCompany = new company();
aCompany.companyid = 43;
aCompany.companyidSpecified = true;

string[] multiOptions = { "Yellow", "Blue" }; // choosen options
aCompany.multifield = new multiselectfield();
aCompany.multifield.multiselectfieldname = "multifield";
aCompany.multifield.records = multiOptions;

companyList[0] = aCompany;
updateresult aresult = binding.update("company", companyList);
if(aresult.updatesuccess == true)
{
MessageBox.Show(aresult.numberupdated + " Records Updated.");
}
else
{
MessageBox.Show("Update failed without exception, contact system administrator");
}
}

Using the UpdateRecord method

private static void UpdateACompanyRecord()
{
String idString = "43";
String newName = "3G Homes";
if((idString != "") & & (newName != ""))
{
crmrecord[] companyList = new crmrecord[1];
crmrecord aNewCompany = new crmrecord();
aNewCompany.entityname = "company";
aNewCompany.records = new recordfield[3];
aNewCompany.records[0] = Getrecordfield("companyid", idString,"integer");
aNewCompany.records[1] = Getrecordfield("name", newName,"string");

recordfield myMulti = Getrecordfield("multifield", "", "multiselectfield");
myMulti.records = new crmrecord[1];
crmrecord aRec = new crmrecord();
aRec.records = new recordfield[3];
aRec.records[0] = Getrecordfield("multiselectfieldname", "multifield", "");
aRec.records[1] = Getrecordfield("records", "Red", "");
aRec.records[2] = Getrecordfield("records", "Green", "");
myMulti.records[0] = aRec;
aNewCompany.records[2] = myMulti;

companyList[0] = aNewCompany;
updateresult aresult = UpdateRecords(companyList,"company");
if(aresult.updatesuccess == true)
{
MessageBox.Show(aresult.numberupdated + " Records Updated.");
}
else
{
MessageBox.Show("Update failed without exception, contact system administrator");
}
}
}

private static recordfield Getrecordfield(string name, string avalue, string type)
{
recordfield aField = new recordfield();
aField.name = name;
aField.value = avalue;
switch(type)
{
case "string": aField.type = crmrecordtype.@string;
break;
case "datetime": aField.type = crmrecordtype.datetime;
break;
case "integer": aField.type = crmrecordtype.integer;
break;
case "decimal": aField.type = crmrecordtype.@decimal;
break;
case "crmrecord": aField.type = crmrecordtype.crmrecord;
break;
case "multiselectfield": aField.type = crmrecordtype.multiselectfield;
break;
}
aField.typeSpecified =true;
return aField;
}

private static updateresult UpdateRecords(ewarebase[] updateList, string entityName)
{
if(updateList != null)
{
return binding.updaterecord(entityName, updateList);
}
return new updateresult();
}

I have to thank my colleagues in Dublin for this.