You don't need to iterate to change the dictionary.
Try
dict.Remove(keyToUpdate);
dict.Add(newKey, value);
You will not be able to change the collection while you are iterating through it.
A way out is to create a temporary list of key value pairs, iterate through this list and change the key as appropriate.