Поскольку я пока не могу комментировать комментарий пользователя 3556956, вот ответ для python3:
connection.append('INBOX', '', imaplib.Time2Internaldate(time.time()), str(new_message).encode('utf-8'))
Короче говоря, вы должны передать сообщение в виде байта вместо строки Python.