A Subject-nél valamit trükközni kell (most jutott eszembe), ezt nézd meg (lehet, hogy vonatkozik más header mezőkre is):
http://bitprison.net/php_mail_utf-8_subject_and_message
Hogy ezt az smtplib megcsinálja-e azt nem tudom.
Legalábbis régen valami ilyesmi megoldást találtam, amikor szívtam vele.
Thunderbird még mindig nem jeleníti meg rendesen a "nyers" UTF-8 Subject-et.
Ez talán az a kódolás, amit minden szépen megeszik: http://en.wikipedia.org/wiki/Quoted-printable
Ha hülyeséget írtam javítsatok ki.