buenas bueno aunque no te soluciones mucho tu problema te puedo dejar un paginador que es el que yo tengo y funciona a la perfeccion solo tienes que adaptarlo a tu web, yo le he echo asta ordenacion por nombre de usuario y fecha nacimiento
phppaginator