Yes, it does feel great.  The code is cleaner and faster.  The API is
simple and matches all the other key= functions in
min/max/nsmallest/nlargest/groupby.

After more thought, I would like to make one more change and require the
arguments to be keywords such as sort(key=str.lower) but not
sort(str.lower).

The issue is that the cmp= interface has been around so long that it is
ingrained into our thinking and in our code.  Having to write-out the
keyword makes the intent explicit and will avoid accidently passing in a
cmp= function when a key= function was intended.  In Py3.1, the
restriction could be relaxed and l.sort(f) could be accepted for
l.sort(key=f).

For the 2-to-3 tool, I wrote a converter that automatically transitions
code currently using a custom compare function:

2.6 code:  s.sort(cmp=lambda p, q: cmp(p.lower(), q.lower()))
3.0 code:  s.sort(key=CmpToKey(lambda p, q: cmp(p.lower(), q.lower())))

Ideally, the automatcic conversion would be accompanied by a suggestion
to manually rewrite to something like:

3.0 code:   s.sort(key=str.lower)

--- converter code ---

def CmpToKey(mycmp):
    'Convert a cmp= function into a key= function'
    class K(object):
        def __init__(self, obj, *args):
            self.obj = obj
        def __cmp__(self, other):
            return mycmp(self.obj, other.obj)
    return K