Why can't we change values of a dictionary while enumerating its keys?

Because the values and keys are stored as a pair. There is not a separate structure for keys and values but instead a single structure which stores both as a set of pair values. When you change a value it necessitates changing the single underlying structure which contains both keys and values.

Does changing a value necessarily change the order of the underlying structure? No. But this is an implementation specific detail and the Dictionary<TKey,TValue> class, correctly, deemed not to reveal this by allowing modification of values as part of the API.

I see where you're coming from, actually. What most of the answers here fail to notice is that you are iterating across the list of Keys, and not the Dictionary's Items themselves. If the .NET framework programmers wanted to, they could fairly easily differentiate between changes made to the structure of the dictionary and changes made to the values in the dictionary. Nevertheless, even when people iterate across the keys of a collection, they usually end up getting the values out anyway. I suspect the .NET framework designers figured that if you're iterating across those values, you'll want to know if something is changing them out from under you, just as much as with any List. Either that or they didn't see it as an important enough issue to merit the programming and maintenance that would be required to differentiate between one kind of change and another.

Thanks to Vitaliy I went back and looked at the code some more and it looks like it is a specific implementation decision to disallow this (see snippet below). The Dictionary keeps a private value called verrsion which is incremented when changing the value of an existing item. When the enumerator is created it makes a note of the value at that time, then checks on each call to MoveNext.

for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next)
{
    if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
    {
        if (add)
        {
            ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
        }
        this.entries[i].value = value;
        this.version++;
        return;
    }
}

I don't know of a reason why this would be necessary. You are still free to modify the properties of the value, just not assign it to a new value:

public class IntWrapper
{
  public IntWrapper(int v) { Value = v; }
  public int Value { get; set; }
}

class Program
{
  static void Main(string[] args)
  {
    var kvp = new KeyValuePair<string, int>("1",1);
    kvp.Value = 17;
    var dictionary = new Dictionary<string, IntWrapper>(){
      {"1", new IntWrapper(1)}, 
      {"2", new IntWrapper(2)}, 
      {"3", new IntWrapper(3)} };

    foreach (var s in dictionary.Keys)
    {
      dictionary[s].Value = 1;  //OK
      dictionary[s] = new IntWrapper(1); // boom
    }
  } 
}