Well, now I've made my own MySQL with help from a lot of drawings, and I think this should be the way to go, IF (and only in exactly this case): - You are going to move a node from one parent to another. In other words - DON'T use this for moving to "top-level" (yet). I haven't tested it yet.
Though it should be bulletproof for moving a sub-tree to another parent (no matter what level the new parent is on). :-)
$query = $this->prepare("
SELECT
@node_id := :nodeID, #id of the node, you're moving.
@node_pos_left := :nodeLeft, #left value of the node, you're moving
@node_pos_right := :nodeRight, #right value of the node, you're moving
@parent_id := :parentID, #id of the parent node, you're moving to
@parent_pos_right := :parentRight; #right value of the parent node, you're moving to.
SELECT
@node_size := @node_pos_right - @node_pos_left + 1;
SELECT
@node_id := :nodeID,
@node_pos_left := :nodeLeft,
@node_pos_right := :nodeRight,
@parent_id := :parentID,
@parent_pos_right := :parentRight;
SELECT
@node_size := @node_pos_right - @node_pos_left + 1;
UPDATE ss_C_Categories
SET Lft = 0-(Lft), Rgt = 0-(Rgt)
WHERE Lft >= @node_pos_left AND Rgt <= @node_pos_right;
UPDATE ss_C_Categories
SET Lft = Lft + @node_size
WHERE Lft >= @parent_pos_right;
UPDATE ss_C_Categories
SET Rgt = Rgt + @node_size
WHERE Rgt >= @parent_pos_right;
UPDATE ss_C_Categories
SET Lft = 0 - (Lft) + (@parent_pos_right - @node_pos_right + 1)
WHERE Lft < 0;
UPDATE ss_C_Categories
SET Rgt = 0 - (Rgt) + (@parent_pos_right - @node_pos_right + 1)
WHERE Rgt < 0;
UPDATE ss_C_Categories
SET Lft = Lft - @node_size
WHERE
Lft > @node_pos_right;
UPDATE ss_C_Categories
SET Rgt = Rgt - @node_size
WHERE
Rgt > @node_pos_right;
UPDATE
".DB_PREFIX."C_Categories
SET
CategoryName = :name,
MetaTag = :metatag,
ParentID = @parent_id,
Description = :desc
WHERE
CategoryID = @node_id
ORDER BY
CategoryID desc
LIMIT 1;
");
$params = array(
array('nodeLeft', $nodeLeft, 'INT'),
array('nodeRight', $nodeRight, 'INT'),
array('nodeID', $nodeID, 'INT'),
array('parentRight', $parentRight, 'INT'),
array('parentID', $parentID, 'INT'),
array('name', $data['name'], 'STR'),
array('metatag', $data['metatag'], 'STR'),
array('desc', $data['description'], 'STR')
);
$this->exec($query, $params);
Again with inspiration from the link in the question.