Fixing broken permissions for deleted user

I have a PostgreSQL 7.4.14 database that is being backed up nightly
using pg_dump. Some time back, we deleted a user from the server that
was no longer employed. This in turn caused some problems with ownership
of some of the tables (since the user didn't exist, the database could
only go by the user ID the the catalog, which made the dumped confused).
We are able to fix those tables relatively easily using ALTER TABLE
table_name OWNER TO new_owner.

The problem we face are with the permissions on some tables. There are a
few tables that were originally created by this deleted user which  in
turn also granted some additional permissions to others. Here is an
example what what \dp shows now (hopefully word wrap is nice to me):

|   Table    |                    Access privileges
+------------+----------------------------------------------------
| menu_items | {101=a*r*w*d*R*x*t*/101,justinp=a*r*w*d*R*x*t*/101}

The deleted user had ID 101 (obviously). If I'm reading the permissions
right, my user account may have even been owner of the table at some
time, but not currently. My understanding of the REVOKE command is that
it will run with the same permissions as the person who first created
the table, thus if I try to revoke any existing permissions on the
table, it says it succeeds, but the permissions are not actually changed
since user 101 does not exist. Looking at the SQL code that psql
actually runs to get the permissions, I see it pulls the data from
pg_catalog.pg_class.relacl (column type aclitem[]). I have a feeling I
should not be trying to modify that column directly.

I am also having this same error message for one of the pg_toast tables
(which is even harder for me to find). Here are the exact error messages:

pg_dump: WARNING: owner of data type "menu_items" appears to be invalid
pg_dump: WARNING: owner of data type "pg_toast_47831338" appears to be
invalid

So what's the trick to fixing these permissions? Obviously I could dump
the database, ignore the errors and then reimport it, but it's a heavy
trafficked production machine and I'd like to avoid downtime if possible.

Thanks.

Justin Pasher