Are you autovacuuming and analyzing aggressively enough? Is there bloat or other concern for these system tables? I expect it may be a concern based on what I remember about your environment having thousands of tables and perhaps autovacuum not keeping up (re: Too slow to create new schema and their tables, functions, triggers).
Can you check results for last (auto)vacuum and analyze? select * from pg_stat_all_tables where relname IN( 'pg_class', 'pg_attribute', 'pg_index' );
