Вот простой код:
$db_link = mysql_connect($hostname,$username,$password) or die("Не могу создать соединение ");
mysql_select_db($dbName) or die("Не могу выбрать базу данных ");

$sql = "select * from table";
if ($result = mysql_query($sql))
echo "Количество записей в таблице = ".mysql_num_rows ($result);
else
die ("ошибка при запросе к DB: ".mysql_error());

Выдает 0 строк, хотя записи есть. Есть ли версии, почему не работает?

phpMyAdmin есть? Попробуйте в нем выполнить этот запрос. Если нет, можно еще попробовать в консоли

у вас реально таблица называется table?