Issue #<3921> may be the same problem.

Sending Gmail by smtplib fails on Python 3.0 and 3.0.1.
It seems to be exist two problems in encode_plain function in smtplib.py:
  * parameter of encode_base64 must be bytes, not str,
  * by default, encode_base64 adds extra newline.
The following is an example of patch.

# original version
def encode_plain(user, password):
    return encode_base64("\0%s\0%s" % (user, password))

# fixed version. Note that "eol=''" is given in Python 2.6's smtplib.
def encode_plain(user, password):
    s = "\0%s\0%s" % (user, password)
    return encode_base64(s.encode('ascii'), eol='')