mysql_query() transfers all result records from the MySQL into the php pcrocess before it returns (unlike mysql_unbufferd_query()). That alone would make the mysql_num_rows() version slower.
Furthermore for some engines (like MyISAM) MySQL can serve a Count(*) request from the index of the table without hitting the actual data. A SELECT * FROM foo
on the other hand results in a full table scan and MySQL has to read every single dataset.