Non ho letto tutte le librerie citate, ho dato solo uno sguardo alla classe che Andrea ha messo su PHPClasses.
Per spostare un nodo ho visto che crea una tabella temporanea, siccome non mi piaceva ho perso un po' di tempo a scrivere un altro metodo (che sicuramente qualcuno altrove avrà già trovato, non penso di aver inventato nulla).

In ogni modo, con il metodo che ho scritto si può spostare un qualsiasi sottoalbero (un nodo con tutti gli eventuali discendenti) in qualsiasi posizione (prima di un altro nodo, dopo un altro nodo, come figlio di un nodo foglia) utilizzando solo una SELECT (senza JOIN o Subquery) e 4 UPDATE.

Considerando che per l'inserimento servono UNA INSERT e 2 UPDATE, mi sembra sia abbastanza buono, come risultato.

Se può interessare posto il codice, così magari mi aiutate a trovare eventuali bug.
Se non interessa... pazienza