If you have a look at the CRM base tables (eg: AccountBase) in MSCRM, you would notice that all columns of Picklist datatype seem to store Integer values. So from where exactly does CRM get the actual text value to be displayed on the UI?
Well, this comes from a not so well known table called 'StringMap'. MSCRM stores all related option values for any picklist in this table.
InsertOptionValueRequest insertOptionValueRequest =
    new InsertOptionValueRequest
{
    AttributeLogicalName = "new_picklist",
    EntityLogicalName = Contact.EntityLogicalName,
    Label = new Label("New Picklist Label", _languageCode)
};

 // Execute the request.
int insertOptionValue = ((InsertOptionValueResponse)_serviceProxy.Execute(
    insertOptionValueRequest)).NewOptionValue;

 Console.WriteLine("Created {0} with the value of {1}.",
    insertOptionValueRequest.Label.LocalizedLabels[0].Label,
    insertOptionValue);
Here's the Structure of the StringMap Table:
Column Name
Description
StringMapId
Primary ID of the record
ObjectTypeCode
Object Type Code of the entity
AttributeName
Schema Name of the picklist attribute
AttributeValue
Integer value of the picklist option. This value is actually stored in the base tables.
LangId
Language Code
OrganizationId
Organization ID
Value
text value displayed within the picklist on the CRM UI
DisplayOrder
Order of the values in the picklist on the CRM UI
VersionNumber
Last updated Timstamp (used during synchronization process)

Modifying the StringMap table to add new values is not recommended and can cause undesired results. In fact CRM does not support modifying any of the CRM tables directly. All updates are to be made via the CRM UI or Web Services.

 CRM seems to store picklist values in 2 tables:
1. StringMap
2. Metadataschema.AttributePicklistValue (This seems to be used as a temporary table)
Whenever an option value is added/edited/deleted for any picklist and saved from the UI, CRM updates the METADATASCHEMA.AttributePicklistValue table. Upon publish of the Form the values are pushed into the StringMap table based on the values in the above table.
Hence directly updating the StringMap table via Sql with new values won’t suffice, since CRM will replace the values in DB with the new values, when the Entity is published via the UI.
There are 2 possible ways to edit picklist values:
1. The Metadata Service (The only SUPPORTED way to add/edit/delete picklist values)
2. Modifying the Entity xml. (This requires editing the xml file for an entity)(UNSUPPORTED)

 Newly created values for any system picklist will have a value of 200000 or greater. This is to maintain backward compatibility during upgrades from CRM 3.0. This ensures that upto 199999 values for any picklist from CRM 3.0 will be successfully transferred during an upgrade to CRM 4.0
Note: Newly created values for any custom picklist would however start from 1.

 Below is an example of both the options:
Option 1:
   InsertOptionValueRequest insertOptionValueRequest =
                new InsertOptionValueRequest
                {
                    AttributeLogicalName = "new_timezone",
                    EntityLogicalName = Account.EntityLogicalName,
                    Label = new Label("New Picklist Label", 1033)
                };
            //Execute the Insert Request
            InsertOptionValueResponse insertResponse = (InsertOptionValueResponse)_serviceProxy.Execute(insertOptionValueRequest);

 Option 2:

 Export the required entity. (MSCRM-Settings-Customization-Export Enitities) OR use the ExportXmlRequest and ExportXmlResponse if you want to perform the export via web services.
Open the file within an xml Editor.
Search for the attribute schemaname you want to update.
You should find something similiar to the text given below
                <options>
                <option value="1">
                  <labels>
                   <label description="Buyer" languagecode="1033" />
                  </labels>
                </option>
                <option value="2">
                  <labels>
                    <label description="Seller" languagecode='1033" />
                  </labels>
                </option>
              </options>
An additional option node would need to be created for every new option you want to add.
Eg :
          <option value="200000">
                  <labels>
                    <label description="Re-Seller" languagecode="1033" />
                  </labels>
                </option>
You can use the ImportXmlRequest/ ImportXmlResponse and PublishXmlRequest/ PublishXmlResponse classes to publish the xml back into CRM.