There is a similar problem that I found with encode_cram_md5 in 
smtplib.py, SMTP.login() method. I used the solution proposed by miwa, 
both for PLAIN and CRAM MD5 authentication. Additionally, for the last 
one, I had to introduce a second correction and byte encode the 
password string when passing it to hmac.HMAC.  

I do not know if I did things correctly, but just in case it can help  
here is the complete patch that I used and worked well with the two 
AUTH methods. I keep the original and modified lines for clarity.

def encode_cram_md5(challenge, user, password):
            challenge = base64.decodestring(challenge)
            #response = user + " " + hmac.HMAC(password,    
challenge).hexdigest()
            response = user + " " + hmac.HMAC(password.encode(), 
challenge).hexdigest()
            #return encode_base64(response)
            return encode_base64((response).encode('ascii'), eol='')
            
        def encode_plain(user, password):
            #return encode_base64("\0%s\0%s" % (user, password))
            return encode_base64(("\0%s\0%s" % (user, password)).encode
('ascii'), eol='')