Find duplicates for mixed type values in dictionaries
Your code reads well, and has good documentation. It is pretty pleasant to read.

You could just simplify a bit faithfulrepr by using generator expression and removing the need for the deepcopy:

def faithfulrepr(ds):
    if isinstance(ds, collections.Mapping):
        res = collections.OrderedDict(
            (k, faithfulrepr(v)) for k, v in sorted(ds.items())
        )
    elif isinstance(ds, list):
        res = [faithfulrepr(v) for v in ds]
    else:
        res = ds
    return repr(res)


However this method will fail when fed dictionaries that have variable types as their keys (like {1: 'one', 'two': 2}).

An other take on the problem would involve more computations but can compare elements with the equality operator (which seems to be what you are really interested on). It involves maintaining two lists, one for the list of keys and one for the values, and searching in the list of values if the current one already exist. This is done using index which, unfortunately, is \$O(n)\$ but compares using __eq__:

def tupelize_dict(ds):
    keys, values = [], []
    for key, value in ds.items():
        try:
            index = values.index(value)
        except ValueError:
            values.append(value)
            keys.append([key])
        else:
            keys[index].append(key)
    return dict(zip(map(tuple, keys), values))
    # or the more readable return {tuple(k): v for k, v in zip(keys, values)}