I'm not quite sure why you expect them to be the same. The inputs are
different, after all - in one case, you have a Unicode object with a
single reference to it (from the tuple), in the second case, you have a
Unicode object with many more references:

py> sys.getrefcount(key[1])
2
py> sys.getrefcount((1,u'foo')[1])
5

That makes a difference for cPickle.