After much searching on the net, here is the code to accomplish what I asked for:
from PIL import Image
im = Image.open("logo_256.png")
# PIL complains if you don't load explicitly
im.load()
# Get the alpha band
alpha = im.split()[-1]
im = im.convert('RGB').convert('P', palette=Image.ADAPTIVE, colors=255)
# Set all pixel values below 128 to 255,
# and the rest to 0
mask = Image.eval(alpha, lambda a: 255 if a <=128 else 0)
# Paste the color of index 255 and use alpha as a mask
im.paste(255, mask)
# The transparency index is 255
im.save("logo_py.png", transparency=255)
Source: http://nadiana.com/pil-tips-converting-png-gif
Although the code there does not call im.load(), and thus crashes on my version of os/python/pil. (It looks like that is the bug in PIL).