You should just add 'utf-8'
argument to your MIMEText
calls (it assumes 'us-ascii'
by default).
For example:
# -*- encoding: utf-8 -*-
from email.mime.multipart import MIMEMultipart
from email.mime.text import MIMEText
msg = MIMEMultipart("alternative")
msg["Subject"] = u'テストメール'
part1 = MIMEText(u'\u3053\u3093\u306b\u3061\u306f\u3001\u4e16\u754c\uff01\n',
"plain", "utf-8")
msg.attach(part1)
print msg.as_string().encode('ascii')