$pagina = $_GET["pagina"];
Estás seguro de que estás pasando esta variable a la página? Estás seguro de que la pasas pasando con un valor correcto???
     echo "<a href='index_paginacion.php?pagina=" . $i . "&criterio=" . $txt_criterio . "'>" . $i . "</a> ";
Este error, viene por esto....
$criterio = "";
if ($_GET["criterio"]!=""){
   $txt_criterio = $_GET["criterio"];
   $criterio = " where nombre like '%" . $txt_criterio . "%'";
}
En este caso....sino se cumple la condición, entonces no se crea la variable $txt_criterio....El hecho de que no necesites declarar las variables en PHP, no significa que no te vaya a dar error por no utilizarlas correctamente  

  Lo mejor sería...
-   
- if (isset($_GET["criterio"])) 
- { 
- ... 
- } 
-   
-   
Saludos,
Blag  
