PHP - Matriz de lista não ordenada (UL) aninhada simples

Isso deve fazer o truque:

$result = mysql_query("SELECT * FROM News");
$topicname = '';

// open list of topics
echo '<ul>';

// loop through topics
while($row = mysql_fetch_array($result)) {
    if (!$row['TopicID']) {
        // fake topic name for unsorted stuff
        $row['TopicName'] = 'Sort Me';
    }
    if ($topicname != $row['TopicName']) {
        if($topicname != ''){
            // had a topic name, means we opened a list
            // that hasn't been closed, close it.
            echo '</ul>';
        }
        // print this topic and open the list of articles
        echo '<li>' . $row['TopicName'] . '</li><ul>';
        // update the current topic to be this TopicName
        $topicname = $row['TopicName']; 
    }
    // the news item
    echo '<li>' . $row['NewsID'] . '"</li>';
}
if($topicname != ''){
    // we saw at least one TopicName, we need to close
    // the last open list.
    echo '</ul>';
}
// end topic list
echo '</ul>';

Acho que seu verdadeiro problema é que você estava abrindo duas listas de cada vez, mas fechando apenas uma (mesmo movendo o último bloco dentro da lista).

Para a segunda parte da sua (nova) pergunta:

Ressalto que, para listas maiores (digamos, mais de 300 itens), a troca que estou fazendo com relação a armazenar a lista na memória e iterar duas vezes, em vez de apenas consultar as contagens necessárias, mudaria para o outro lado. Ou seja, a solução abaixo coloca tudo na memória e, em seguida, itera uma segunda vez para imprimi-lo; uma alternativa seria executar duas consultas, uma para localizar o número de TopicNames exclusivos e outra para localizar o número total de itens na lista.

Além disso, para exibição, você realmente quer resolver alguma otimização para layout, vou fazer isso ingenuamente e apenas fazer um número (aproximadamente) igual de tópicos por coluna e quando a divisão não funcionar, isso pesará para a esquerda. Você verá onde pode ajustar ou substituir algum código para obter resultados diferentes (e melhores?).

$columns = // user specified;

$result = mysql_query("SELECT * FROM News");
$num_articles = 0;

// $dataset will contain array( 'Topic1' => array('News 1', 'News2'), ... )
$dataset = array();
while($row = mysql_fetch_array($result)) {
    if (!$row['TopicID']) {
        $row['TopicName'] = 'Sort Me';
    }
    $dataset[$row['TopicName']][] = $row['NewsID'];
    $num_articles++;
}

$num_topics = count($dataset);

// naive topics to column allocation
$topics_per_column = ceil($num_topics / $columns);

$i = 0; // keeps track of number of topics printed
$c = 1; // keeps track of columns printed
foreach($dataset as $topic => $items){
    if($i % $topics_per_columnn == 0){
        if($i > 0){
            echo '</ul></div>';
        }
        echo '<div class="Columns' . $columns . 'Group' . $c . '"><ul>';
        $c++;
    }
    echo '<li>' . $topic . '</li>';
    // this lists the articles under this topic
    echo '<ul>';
    foreach($items as $article){
        echo '<li>' . $article . '</li>';
    }
    echo '</ul>';
    $i++;
}
if($i > 0){
    // saw at least one topic, need to close the list.
    echo '</ul></div>';
}