To update a value in version 10 and up (thanks Vlad for the heads up):

ALTER TYPE status_enum RENAME VALUE 'waiting' TO 'blocked';

To remove a value in any version or update a value in version 9.6 and bellow:

# rename the existing type
ALTER TYPE status_enum RENAME TO status_enum_old;

# create the new type
CREATE TYPE status_enum AS ENUM('queued', 'running', 'done');

# update the columns to use the new type
ALTER TABLE job ALTER COLUMN job_status TYPE status_enum USING job_status::text::status_enum;
# if you get an error, see bottom of post

# remove the old type
DROP TYPE status_enum_old;