I have a ridiculously large database at work, with a multitude of tables, and had the same problem. However, using a select count(*) from tablename wasn't terribly efficient, so I ran sp_spaceused instead, which is fine in most cases:
CREATE TABLE #spaceused
(name varchar(20), rows int...