It should be noted that the unicode aspect of this bug is actually a recognized flaw with a nontrivial solution.  See this thread from the Python-dev list, dated from July 2006:

http://mail.python.org/pipermail/python-dev/2006-July/067248.html

It was essentially agreed upon in this thread that the "obvious" solution--simply converting to UTF-8 as per rfc3986--doesn't actually cover all cases, and that passing a unicode string in to urllib.quote() indeed has ambiguous results.  For more information, see Mike Brown's comment on the aforementioned thread:

http://mail.python.org/pipermail/python-dev/2006-July/067335.html

It was generally agreed in the thread that the proper solution was to have urllib.quote() *only* deal with standard Python string data, and to raise a TypeError if a unicode string is passed in, implying that any conversion needs to be done by higher-level code, because implicit conversion within urllib.quote() is too ambiguous.

However, it seems the TypeError fix was never made to the Python SVN repository; perhaps this is because it may have broken legacy code that actually catches KeyErrors as John Nagle mentioned?  Or perhaps it was simply because no one ever got around to it.  Unfortunately, I'm not in a position to say for sure, but I hope my explanation helps.