Как правильно использовать юникод в python 2.7?
Лучше просто перейдите на python3, это менее болезненно
Если кому интересно, в 2.7 решил примерно вот таким вот костылем:...
def _repl_unicode(matchobj):
	line3 = re.sub('\\\\uffffff','',matchobj.group(0))
	line4 = binascii.unhexlify(line3)
	return line4

while True:
	line2_obj = re.search('((\\\\uffffff[0-9a-f]{2}){2})',line)
	if line2_obj is not None:
		line2 = line2_obj.group(0)
		line3 = re.sub('\\\\uffffff','',line2)
		line = re.sub('((\\\\uffffff[0-9a-f]{2}){2})',_repl_unicode,line)
	else:
		break
...
И вуаля, на выходе уже вполне себе нормальная кириллица.