Hola,
El problema puede ser que no propages el criterio en los links de la paginacion. Los links de las paginas deben ser del estilo:
Código PHP:
<a href="paginacion.ph?pagina=<?php echo $i; ?>&criterio=<?php $txt_criterio; ?>">
O como lo generes.
Tambien date cuenta que solo recoges el criterio de la URL. Si llegas a la paginacion desde un formulario cuyo campo sea 'criterio', este codigo solo te funcionara si el method del formulario es GET. Si es POST, ademas de leer $_GET, debes comprobar $_POST, y coger el valor correspondiente.
Tambien por paranoias mias, te recomendaria que no llamases igual la variable $criterio y el parametro $_GET['criterio']. Mas que nada, porque no se exactamente como estan relacionadas ambas variables en caso de register_globals a ON. Quizas apuntan al mismo "hueco" de memoria, y si cambias una cambias la otra. Y como empiezas con un $criterio="", puede que estes borrando el contenido de $_GET['criterio'] (luego intento comprobar este extremo).
Espero no haberte liado mas.
Suerte.