I ran into the problem of not being able to get beyond the first page when sorting by top-level categories. 2nd level category pagination worked. The problem was I had duplicate category names and this occurred through the import. I didn't think it was going to be a problem because they subcategories had different parents, but it was. So, if you have pagination problems, check to be sure no categories have the same name.