На днях столкнулся с проблемой: упаковал архив в винде, скопировал его в линух, распаковал банально tar’ом и минут пять тупо глядел на файлы вроде «?????????.xml» и «?????????.mbx».
На гугление решения ушло минут тридцать. В результате нашлось замечательное решение:

#!/usr/bin/env python

import tarfile
import sys

if len(sys.argv) == 1:
    print "usage: %s <tar archive>" % (sys.argv[0])
    sys.exit(0)

arhive_name = sys.argv[1]

archive_encoding = 'cp1251'

def recover(name):
    return unicode(name, archive_encoding)

tar = tarfile.open(name=arhive_name, mode='r', bufsize=16*1024)
updated = []
for m in tar.getmembers():
    m.name = recover(m.name)
    updated.append(m)

tar.extractall(members=updated)
tar.close()

За сие изящное решение спасибо baltazar’у.