У вас неправильная структура данных для того, что вы пытаетесь сделать.
Используйте это вместо.
dict1 = {'a': [(1, 2), (3, 4)], 'b': [(1, 2), (5, 6)]}
dict2 = {'a': [(1, 2), (5, 6)], 'b': [(1, 2), (7, 8)]}
Жизнь проще, когда вы пытаетесь выполнять операции над множествами неизменяемых объектов, таких как кортежи.
Это преобразует ваш список списков в список списков.
>>> dict( (key,[tuple(v) for v in dict1[key]]) for key in dict1 )
{'a': [(1, 2), (3, 4)], 'b': [(1, 2), (5, 6)]}
Вот полное решение.
>>> dict1t= dict( (key,[tuple(v) for v in dict1[key]]) for key in dict1 )
>>> dict2t= dict( (key,[tuple(v) for v in dict2[key]]) for key in dict2 )
>>> set(dict1t['a'])-set(dict2t['a'])
set([(3, 4)])