I had this problem again in WP 3.0.1 after importing several XMLs from another blog into my blog using the official WordPress Importer 0.2 plugin, merging tags and categories. The effective number of pages of categories did not reflect the real number of categories present in the database, because even if the total pages were 9 after the 6th they were empty.
To fix this I had to delete the option named “category_children”, so that it was autoamtically recalculated by WP again when I went back to the Categories menù in the dashboard.
I’ll leave it here as a memo for me or for anyone who could find it useful.