tl;dr:

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;

PSQL provides an easy way to add new values to an enum: ALTER TYPE name ADD VALUE .... Version 10 introduced an easy way to update existing values: ALTER TYPE name RENAME VALUE .... Unfortunately, there is no way to remove values in any version (as of 12) and no way to update values in 9.6 and bellow. The most popular solutions I found for this problem were always one of these two:

"Drop and re-create the type."
This solution alone is no good if the type is already in use as you would have to drop any columns that use the type or temporarily change the column type to TEXT. This has some (slight) disadvantages and there is a sleeker solution.

"Modify the system tables with DELETE FROM pg_enum..."
No! hacking the catalogs is dangerous, unpredictable, and almost always a bad idea.

Instead, lets create a new type with the correct enum values and swap out the old one. This way we don't have to drop and recreate columns nor modify system tables.

Example Scenario

CREATE TYPE status_enum AS ENUM('queued', 'waiting', 'running', 'done');

CREATE TABLE job (
  id         int,
  job_status status_enum
);

INSERT INTO job VALUES
  (1, 'queued'),
  (2, 'waiting'),
  (3, 'running'),
  (4, 'done');

Removing a Value

Lets say we want to remove the waiting status and set all waiting jobs to running.

# remove references to the deprecated value
UPDATE job SET job_status = 'running' WHERE job_status = 'waiting';

# 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;

Updating/Renaming a Value

Lets say we decided blocked was a better description than waiting. In this case we are simply adding a new value (blocked) and removing an existing value (waiting). So, the process is the same as above except we must add our new value to the existing enum first.

# add the new value to the existing type
ALTER TYPE status_enum ADD VALUE 'blocked';

# update references to the deprecated value
UPDATE job SET job_status = 'blocked' WHERE job_status = 'waiting';

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

# create the new type
CREATE TYPE status_enum AS ENUM('queued', 'blocked', '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;

Errors

• invalid input value for enum {enum name}: "{some value}" - One or more rows have a value ("{some value}") that is not in your new type. You must handle these rows before you can update the column type.
• default for column "{column_name}" cannot be cast automatically to type {enum_name} - The default value for the column is not in your new type. You must change or remove the default value for the column before you can update the column type. Thanks to Philipp for this addition.