dict1 = {'London': {'car_toyota': 288, 'car_audi': 64, 'car_bmw': 426}, 'Paris': {'car_toyota': 48, 'car_audi': 96}, 'New York': {'car_bmw': 48}

dict2 = {'car_toyota': 'Toyota', 'car_audi': 'Audi', 'car_bmw': 'BMW'}

{'London': {'Toyota': 288, 'Audi': 64, 'BMW': 426}, 'Paris': {'Toyota': 48, 'Audi': 96}, 'New York': {'BMW': 48}

for i, j in dict1.iteritems():
    for k, v in j.items():
        for a, b in dict2.items():
            if k == a:
                j[k] == j.pop(a)