Bueno, he encontrado la solución, quizá no es la mejor, pero funciona:
  
Código:
 //Código de truman_truman adaptado a mis necesidades:
function menu( $id_padre = 0 ){      
         $menu = ''; 
         $sql = "SELECT * FROM menu WHERE id_padre = $id_padre ORDER BY orden";      
         $query = mysql_query( $sql,con() );   
         $cant = mysql_num_rows( $query );           
         if( $cant > 0 ){ $menu .= '<ul>'; }             
         while( $row = mysql_fetch_assoc( $query ) ){
            $menu .=  '<li id="articulo-'.$row['id'].'"><a href="'.crear_url($row['id'], "menu").'">'.$row['menu_nombre'].'</a>'; 
            $menu .= menu( $row['id'] ) . '</li>';               
         }          
         if( $cant > 0 ){ $menu .= '</ul>'; }        
         return $menu; 
} 
//Código que he reutilizado que me generaba 'breadcrumbs', ahora lo uso para generar los links
function crear_url($id, $category_tbl) {
    $sql = "SELECT * FROM ".$category_tbl." WHERE ID = $id";
	$query = mysql_query( $sql,con() );  
    $row = mysql_fetch_array($query);
    if($row['id_padre'] == 0) {
        return $row['seoname']."/";
    } else {
        return crear_url($row['id_padre'],$category_tbl).$row['seoname']."/";
    }
}
$menu = utf8_encode(menu());
echo '<div id="menu">'.$menu.'</div>';
  Lo único que me preocupa es que se hacen demasiadas consultas a la base de datos, pero es la única solución que he encontrado.