Un error que no veo...

[By_George]

te imprime el else entonces que es donde solo imprimes PREVIO pero sin un link

checa tambien que se imprimia una comilla en la url solo corrigelo asi

echo "<a href=".$_SERVER['PHP_SELF']."?pagina=$pagina_anterior>PREVIO</a>";