I discovered what the problem was :-). It seems that if you add a property to a media type that all media items are updated in the cmsPropertyData table, but if you add a property to a base media type this doesn't happen and that's what is causing the error from my first post. I'm working on a new package which needs to add a new property to some media types. Here at Digibiz we are working with base media types so I needed to find a way to only add this new property to the base media type without breaking all existing media items which have a media type that inherit from another base media type. Here is part of my code to fix this:

//Get the media type which needs to be updated.
MediaType mediaType = new MediaType(Convert.ToInt32(listItem.Value));

//Check if the property already exists.
if (mediaType.getPropertyType("trackLabel") == null)
{
    //Add the new property to the media type.
    PropertyType trackLabel = mediaType.AddPropertyType(new DataTypeDefinition(-88), "trackLabel", "Track label");

    //Add the property to the first tab of the media type.
    mediaType.SetTabOnPropertyType(trackLabel, mediaType.getVirtualTabs[0].Id);

    //Save the changes.
    mediaType.Save();

    string sql = @"
    select c.nodeId, cv.VersionId from cmsContentType ct 
        inner join cmsContent c ON ct.nodeId = c.contentType
        inner join cmsContentVersion cv ON c.nodeId = cv.ContentId
    where ct.masterContentType = @mediaTypeId";

    //Get all the media items which have this media type as a base media type.
    using (IRecordsReader dr = SqlHelper.ExecuteReader(sql, SqlHelper.CreateParameter("@mediaTypeId", mediaType.Id)))
    {
        //Loop through all the media items.
        while (dr.Read())
        {
            //Get the id and versionId of a media item.
            int mediaId = dr.GetInt("nodeId");
            Guid versionId = dr.GetGuid("VersionId");

            //Check if this property is in the cmsPropertyData table.
            int count = SqlHelper.ExecuteScalar<int>(@"
            select count(*) from cmsPropertyData
            where contentNodeId = @nodeId
            and versionId = @versionId
            and propertytypeId = @propertytypeId", 
                SqlHelper.CreateParameter("@nodeId", mediaId),
                SqlHelper.CreateParameter("@versionId", versionId), 
                SqlHelper.CreateParameter("@propertytypeId", trackLabel.Id));

            if (count == 0)
            {
                //If there is no row in cmsPropertyData it means that this media item doesn't have the new property yet. 
                //This will only happen when using base media types.
                //By inserting this row into the database this media item will also have the new property.
                SqlHelper.ExecuteNonQuery("INSERT INTO cmsPropertyData (contentNodeId, versionId, propertyTypeId) VALUES(@contentNodeId, @versionId, @propertyTypeId)",
                    SqlHelper.CreateParameter("@contentNodeId", mediaId),
                    SqlHelper.CreateParameter("@versionId", versionId),
                    SqlHelper.CreateParameter("@propertyTypeId", trackLabel.Id));
            }
        }
    }
}

Jeroen