>>> message = "\xd0\xa2\xd0\xb5\xd0\xba\xd1\x81\xd1\x82 \xd0\xb7\xd0\xb0\xd1\x8f\xd0\xb2\xd0\xba\xd0\xb8"
>>> print message
Текст заявки
>>>

# -*- coding: utf-8 -*-
message = "\xd0\xa2\xd0\xb5\xd0\xba\xd1\x81\xd1\x82 \xd0\xb7\xd0\xb0\xd1\x8f\xd0\xb2\xd0\xba\xd0\xb8"
msg =  unicode(message, encoding='utf-8')
msg = msg.encode('utf-8')

for uid, data in messages.iteritems():

	msg = email.message_from_string(data['RFC822'].encode('utf8'))

msg = email.message_from_string(data['RFC822'])

  File "/usr/lib/python2.7/email/__init__.py", line 57, in message_from_string
    return Parser(*args, **kws).parsestr(s)
  File "/usr/lib/python2.7/email/parser.py", line 82, in parsestr
    return self.parse(StringIO(text), headersonly=headersonly)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 1370-1389: ordinal not in range(128)

>>> import email
>>> em = u'\u0422\u0435\u043a\u0441\u0442 \u0437\u0430\u044f\u0432\u043a\u0438'
>>> em
'Текст заявки'
>>>
>>> e = email.message_from_string(em)
>>> e.as_string()
'\nТекст заявки'
>>>

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import email
message = "\xd0\xa2\xd0\xb5\xd0\xba\xd1\x81\xd1\x82 \xd0\xb7\xd0\xb0\xd1\x8f\xd0\xb2\xd0\xba\xd0\xb8"
em = email.message_from_string(message)
print em.as_string()