Tu problema está aqui:
$criterio = "";
if ($_POST["apellidos"]!=""){
$txt_criterio = $_POST["apellidos"];
$criterio = "where APELLIDO like '%".$txt_criterio."%' order by idContacto";
}
Ya que tu link de conexión es a través del metodo GET y no POST, por lo que el "criterio" se elimina al pasar a la siguiente pagina...
Una posible solución sería sustituir lo anterior por esto:
Código PHP:
$criterio = "";
if ($_POST["apellidos"]!=""){
$txt_criterio = $_POST["apellidos"];
} elseif ($_GET["criterio"]!="") {
$txt_criterio = $_GET["criterio"];
}
$criterio = "where APELLIDO like '%".$txt_criterio."%' order by idContacto";
Saludos!