How to modify key in a dictionary in C#

As Jason said, you can't change the key of an existing dictionary entry. You'll have to remove/add using a new key like so:

// we need to cache the keys to update since we can't
// modify the collection during enumeration
var keysToUpdate = new List<int>();

foreach (var entry in dict)
{
    if (entry.Key < MinKeyValue)
    {
        keysToUpdate.Add(entry.Key);
    }
}

foreach (int keyToUpdate in keysToUpdate)
{
    SortedDictionary<string, List<string>> value = dict[keyToUpdate];

    int newKey = keyToUpdate + 1;

    // increment the key until arriving at one that doesn't already exist
    while (dict.ContainsKey(newKey))
    {
        newKey++;
    }

    dict.Remove(keyToUpdate);
    dict.Add(newKey, value);
}

You need to remove the items and re-add them with their new key. Per MSDN:

Keys must be immutable as long as they are used as keys in the SortedDictionary(TKey, TValue).