I can't seem to post a comment, so I'll just say that updating pg_enum works in Postgres 8.4 . For the way our enums are set up, I've added new values to existing enum types via:
INSERT INTO pg_enum (enumtypid, enumlabel)
SELECT typelem, 'NEWENUM' FROM pg_type WHERE
typname = '_ENUMNAME_WITH_LEADING_UNDERSCORE';
It's a little scary, but it makes sense given the way Postgres actually stores its data.