Properly encode message as unicode, don't just change the string type.

Calling unicode() just changed the internal representation, while
.encode('utf-8') actually converts it into the right bytes.
Requests might do this for us actually, I should look it up.