Identifying equivalent lists
for key in preliminary_key_list:
    key = list(key) # convert from immutable tuple to mutable list


You don't need to do this. Rather then creating a modifiable list, just use the tuple and construct a new tuple at the end

    i = 0
    translation = {}
    counts = [[j, key.count(j)] for j in set(key)]


This should be a list of tuples, not a list of lists. 

    counts_right = [j[1] for j in counts]

    for count in set(key):   


Use for i, count in enumerate(set(key)): to avoid having to manage i yourself.

You use set(key) twice, which will force python to do work twice. Also, there is no guarantee you'll get the same order both times. 

        translation[counts[counts_right.index(max(counts_right))][0]] = i
        counts_right[counts_right.index(max(counts_right))] = 0


These lines are really expensive. max will scan the whole list checking for the highest value. .index will then rescan the list to find the index for the value. 
Then you do the whole thing over again on the next line!

You'd do far better as @GlenRogers suggests to sort by the counts. 

        i += 1

    for i in range(len(key)):
        key[i] = translation[key[i]]


Here using a comprehension would be better (I think):

 key = tuple(translation[item] for item in key)


Here is how I'd write the code:

ret = []
for key in preliminary_key_list:
    counts = sorted(set(key), key = lambda k: -key.count(k) )
    translation = { val: idx for idx, val in enumerate(counts) }
    ret.append([translation[k] for k in key])
return ret