We have a .NET Windows application that runs the following query on login to get some information about the database:

SELECT t.TABLE_NAME, ISNULL(pk_ccu.COLUMN_NAME,'') PK, ISNULL(fk_ccu.COLUMN_NAME,'') FK 
FROM INFORMATION_SCHEMA.TABLES t
LEFT JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS pk_tc 
ON pk_tc.TABLE_NAME = t.TABLE_NAME 
AND pk_tc.CONSTRAINT_TYPE = 'PRIMARY KEY' 
LEFT JOIN INFORMATION_SCHEMA.CONSTRAINT_COLUMN_USAGE pk_ccu 
ON pk_ccu.CONSTRAINT_NAME = pk_tc.CONSTRAINT_NAME 
LEFT JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS fk_tc 
ON fk_tc.TABLE_NAME = t.TABLE_NAME 
AND fk_tc.CONSTRAINT_TYPE = 'FOREIGN KEY' 
LEFT JOIN INFORMATION_SCHEMA.CONSTRAINT_COLUMN_USAGE fk_ccu 
ON fk_ccu.CONSTRAINT_NAME = fk_tc.CONSTRAINT_NAME

Usually this runs in a couple seconds, but on one server running SQL Server 2000, it is taking over four minutes to run. I ran it with the execution plan enabled, and the results are huge, but this part caught my eye (it won't let me post an image):

http://img35.imageshack.us/i/plank.png/

I then updated the statistics on all of the tables that were mentioned in the execution plan:

update statistics sysobjects
update statistics syscolumns
update statistics systypes
update statistics master..spt_values
update statistics sysreferences

But that didn't help. The index tuning wizard doesn't help either, because it doesn't let me select system tables. There is nothing else running on this server, so nothing else could be slowing it down. What else can I do to diagnose or fix the problem on that server?