OK, I was monkeying around some more, and it's relatively painless to move a node as well. I think. This is hardly an optimal test database - it has a whopping twenty entries - but enough to get the idea.

function move_node($parent, $title) {
// This is the whack-a-mole method of moving a node (I was too lazy to calculate exactly
// what would be involved in a manual move). So here's what I do - get the right value
// of the new parent node. Set the parent of the moved node as appropriate. Rebuild the
// database for the current node, then rebuild the entire database. As I say, ugly as sin.

// First, we get the parent's right value
$result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
$row = mysql_fetch_array($result);
$newLeft = $row['rgt'];

// Maybe we should take the root of the entire tree, and rebuild from that? Easy, but time-consuming.
$result = mysql_query('SELECT title FROM tree ORDER BY lft ASC LIMIT 1;');
$row = mysql_fetch_array($result);

// Next, we set the node's new parent.
$result = mysql_query('UPDATE tree set parent="'.$parent.'" WHERE title="'.$title.'";');

// Rebuild the tree from this node down, based on a new left value.
rebuild_tree($title, $newLeft);

// Rebuild the entire DB, because you just clobbered the hell out of it!
rebuild_tree($rootLevel, 1);

... The real disadvantage to this approach is the double-rebuild of the database. I probably don't have to do it, but I figure better safe than sorry. Please do post a quicker or more efficient way of moving nodes, if anybody has one...