Дайджест всегда 20 байтов?len (hashed.digest ()), кажется, всегда равно 20.
hashed = hmac.new(key, signature_base_string, sha)
print hashed.digest()
print len(hashed.digest())
i = 0
for c in hashed.digest():
i = i + 1
print ord(c)
print base64.b64encode(hashed.digest())