\d on database with a lot of tables is slow

I have a client with a database that contains 4000 relations according
to vacuum verbose, and \d in psql is painfully slow. In particular...
  ->  Seq Scan on pg_class c  (cost=0.00..2343.09 rows=6124 width=73) (actual time=0.325..22100.840 rows=16856 loops=1)
      Filter: (((relkind = 'r'::"char") OR (relkind = 'v'::"char") OR (relkind = 'S'::"char") OR (relkind =
''::"char"))AND pg_table_is_visible(oid))
 

That's off my laptop, but they're seeing similar issues on an 8-way
Opteron as well...

I've messed around with adding indexes to a copy of pg_class to no
avail. Any ideas on how to improve the performance?

Also, not sure if this matters, but they're occasionally getting errors
like 'Did not find relation named "table that exists"' (where 'table
that exists' is the name of some table that is in the catalog) from \d.
Does anyone know what causes that?
-- 
Jim C. Nasby, Sr. Engineering Consultant      jnasby@pervasive.com
Pervasive Software      http://pervasive.com    work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461