¿Cómo crear una matriz a partir de este conjunto de resultados (categorías anidadas almacenadas en una base de datos con un modelo transversal)?

Ah, finalmente algo para lo que las referencias son útiles:

<?php
$tree = array(
    array('Cat 1', 'depth' => 0),
    array('Cat 2', 'depth' => 1),
    array('Cat 3', 'depth' => 1),
    array('Cat 4', 'depth' => 2),
    array('Cat 5', 'depth' => 1),
    array('Cat 6', 'depth' => 2),
    array('Cat 7', 'depth' => 3),
    array('Cat 8', 'depth' => 1)
);
//same as before
$currDepth = -1;

//initilialize result
$result = array();

//create path structure for depths
$path = array();

//create 'root' node
$olditem = array('children'=> &$result);


foreach($tree as $item){
    if($item['depth'] > $currDepth){
        //remove possible old reference (old depth of other branch
        if(isset($path[$item['depth']])) unset($path[$item['depth']]);

        //make sure we have an array entry
        if(!isset($olditem['children'])) $olditem['children'] = array();

        //acquire target
        $path[$item['depth']] = &$olditem['children'];
    }
    if($item['depth'] != $currDepth) unset($olditem);
    //set correct target
    $currDepth = $item['depth'];
    //add item
    $path[$currDepth][] = &$item;
    //copy & remove reference
    $olditem = &$item;
    unset($item);
}
//always nice to clean up reference bombs:
unset($path);
unset($olditem);

var_dump($result);
?>