As Antoine said, there's a reason BaseException now implements both
__str__ and __unicode__ and doesn't implement the latter in terms of the
former - it's the only way to consistently support Unicode arguments
that can't be encoded to an 8-bit ASCII string:

>>> str(Exception(u"\xc3\xa0"))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeEncodeError: 'ascii' codec can't encode characters in position
0-1: ordinal not in range(128)
>>> unicode(Exception(u"\xc3\xa0"))
u'\xc3\xa0'

For some of the exception subclasses that will always return ASCII (e.g.
KeyError, which calls repr() on its arguments) then defining __unicode__
in terms of __str__ as Ezio suggests will work.

For others (as happened with BaseException itself), the __unicode__
method will need to be a reimplementation that avoids trying to encode
potentially non-ASCII characters into an 8-bit ASCII string.