Примерно так должно получиться:
>>> d = { (8, 2010) : [2,5,3], (1, 2011) : [6,7,8], (6, 2010) : [11,12,13] }
>>> sorted((i for i in d.iteritems()), key=lambda x: (x[0][1], x[0][0]))
[((6, 2010), [11, 12, 13]), ((8, 2010), [2, 5, 3]), ((1, 2011), [6, 7, 8])]
(Предполагается, что лямбда должна сортироваться сначала по году, а затем по месяцу.)
См. Лучший ответ Алекса Мартелли о том, как использовать itemgetter
для решения этой проблемы.