In pybloom.py line 71 should test if the key is unicode rather than testing if the key is not unicode. If the key is not unicode, encoding it as utf-8 will first attempt to decode the string using the default encoding. Usually this is ascii, so if the string is not ascii a UnicodeDecodeError will be raised. Similarly, if the key is unicode, str(key) tries to encode the key in the default encoding. If the key contains non-ascii characters, this will raise UnicodeEncodeError.