efficient updating of nested dictionaries

[omission9]

I have a dictionary that looks like this
MY_DICT[KEY_X][KEY_Y][KEY_Z]=FOO

I am having a problem updating this with a simple 
MY_DICT.update(NEW_DICT) as update doesn't seem to care about getting 
into the inner dicts.
Getting the keys of each and iterating through and updating each one is 
terribly slow as the number of keys gets bigger and bigger.
What is the bst way to update my nested dicts?