Take a look at the execution plan for your query. You’ll notice that the query is doing an Index Scan (or a table scan), not an Index Seek which is why the SELECT COUNT(*) takes so long. The reason for this is that the COUNT(*) function needs to look at every record in the table.
As a workaround you can use the technique that Microsoft uses to quickly display the number of rights when you right click on the table and select properties.
select sum (spart.rows)
from sys.partitions spart
where spart.object_id = object_id('YourTable')
and spart.index_id < 2
You should find that this returns very quickly no matter how many tables you have.
If you are using SQL 2000 still you can use the sysindexes table to get the number.
where id = object_id('YourTable')
This number may be slightly off depending on how often SQL updates the sysindexes table, but it’s usually corrent (or at least close enough).
(I was informed that my prior information on this post was not quite accurate, so I have revised the post accordingly. In a nutshell when doing a SELECT count(*) FROM Table even if the row contains all NULLs the record is still counted.)