probably not the answer you want to hear, but how about adding a 'count' field to your category table. you would need to create the logic to increment and decrement the count of all higher level categories when you add or remove a listing.
Code:
`category` (
`catid` bigint(6) NOT NULL default '0',
`count` int(10) NOT NULL default '0',
`name` varchar(60) NOT NULL default '',
`description` varchar(255) NOT NULL default '',
`superset` bigint(6) NOT NULL default '0',
`addable` tinyint(1) NOT NULL default '1',
UNIQUE KEY `catid` (`catid`)
) TYPE=MyISAM COMMENT='listing of all categories ';