Vedi se può andar bene così:

codice:
function ScanDirectory($Directory) {

   $MyDirectory = opendir($Directory) or die('Errore');
   while ($currentFile = readDir($MyDirectory)) {
      $theFiles[] = $currentFile;
   };
   closedir($MyDirectory);

   $Files = preg_grep("/^[A-Za-z0-9]/", $theFiles);

   sort($Files);

   echo '<ul>';
   foreach($Files as $Entry) {
      if(is_dir($Directory.'/'.$Entry)) {
         echo '[*]'.$Entry;
         ScanDirectory($Directory.'/'.$Entry);
         echo '';
      } else {
         $cartellautente = $Directory."/".$Entry;
         echo '[*]'."<a href=\"downloadit.php?file={$cartellautente}\">{$Entry}</a>
".'';
      }
   }
   echo '[/list]';
}
Come vedi inizialmente mi scarico tutta la directory in un array.
Poi elimino il "." e il ".." con la preg_grep.
Poi ordino.
E infine faccio un foreach sull'array analogo al while che facevi tu.
Ho anche dato una sistemata agli <ul>.

Ti faccio notare che nell'ordinamento su Linux le maiuscole vengono prima delle minuscole, quindi troverai prima i nomi che iniziano con maiuscole, ordinati, e poi, dopo la "Z" si ricomincia con la "a".

Il risultato non è molto bello, a mio avviso, però il sort lavora così.

Fino a lunedì non mi ricollegherò al forum quindi se non ti va bene spero che possa aiutarti qualcun altro.

Ciao