yo también tuve ese error y lo solucioné asi:
echo " <a class='p' href='".$_SERVER['PHP_SELF']."?pagina=".($pagina+1)."&busqueda=".$nombre."' >";
no sé... mira que lo hayas cambiado en todos los links, y lo de la variable que la pasas por REQUEST...