iPython on OSX had colorized output and TAB-completion worked, so I assumed readline was working, but as soon as I tried to use command history it became a mess. Difficult to describe, but messy :-)

After Googling a bit, found the culprit: when I started iPython, it printed “Leopard libedit detected.”. Turns out that for iPython to work perfectly, libedit won’t do. The fix is trivial:

sudo easy_install readline