El problema que mencionas es común cuando se trata de consultas complejas, a varias tablas, con la cláusula GROUP BY, o que utilizan funciones como COUNT(), SUM(), etc. Algunas pocas veces también ha pasado en consultas más simples.
Para eso fue creada la variable "$_pagi_conteo_alternativo" desde la versión 1.5 de Paginator. Basta con que la setees a true y el problema se arreglará.
$_pagi_sql = "SELECT...";
$_pagi_cuantos = 10;
$_pagi_conteo_alternativo = true;
...
Puedes verlo en el ejemplo de la web: http://jpinedo.webcindario.com/scripts/paginator/ejemplo_avanzado.html
También en la descripción (mira la variable $_pagi_conteo_alternativo):
En la medida de lo posible, yo recomiendo no utilizar esa variable (a menos, claro, que sea necesario como en tu caso), porque utiliza la función mysql_num_rows() para contar, lo cual es más lento que el conteo directo al SQL con COUNT(*).
Bueno... nada más. Tengo que agradecerte por el comentario y por avisar del comportamiento inesperado con el que te encontraste. Espero que con esta respuesta hayas absolvido tus dudas.