> It's definitely a bug in urllib

A bug in what way? Up to 2.6 (*), the docs state nothing about the type of the "string" parameter.
(*) http://docs.python.org/release/2.6.5/library/urllib.html#urllib.quote

I think everyone assumed that the parameter should be a "str" object and nothing else. Apparently some people used it accidentally with some unicode strings and it "worked" until these strings contained non-ASCII characters. But it's a side-effect of how 2.x unicode strings work, and it doesn't seem to me quote() was ever intended to accept unicode strings.

If we were following you, we would add "encoding" and "errors" arguments to any str-accepting 2.x function, so that it can also accept unicode strings. That's certainly not a reasonable solution.