The other guy is most probably using Python 2.7 (or lower), where the str means byte string, not Unicode string as in Python 3.3.

If I were you I'd try changing the str() into a bytes() and remove the encode() at the end.

There're other parts of the auth logic that you haven't shown in your code though (and those might be wrong) - e.g. do you have a monotonically increasing nonce in the post message? Is the post message url-encoded?