Would the following work instead, perhaps faster?

    def renumber_values(d):
        vals = set(d.values())
        mapping = dict(zip(vals, range(len(vals))))
        ret = dict([(k, mapping[v]) for k,v in d.items()])
        return ret