I did some more testing and verified that this is a problem caused by the fact that trans_5C is a string and not unicode. It also happens when trans_36 is sent to key.translate().

Python 2.7.3 (default, Aug  1 2012, 05:14:39) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import hmac
>>> hmac.new(u'key', u'msg')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "hmac.py", line 132, in new
    return HMAC(key, msg, digestmod)
  File "hmac.py", line 72, in __init__
    self.inner.update(key.translate(trans_36))
TypeError: character mapping must return integer, None or unicode
>>>