Il tuo codice è corretto, a parte che generi due </select> (quello fuori dal PHP dovresti eliminarlo), ma ciò non dovrebbe inficiare la selezione di default. Inoltre aggiungerei uno spazio dopo il selected, cioè echo 'selected="SELECTED" ';, ma anche questa è una modifica stilistica più che strutturale.

La condizione più ovvia per cui non si seleziona un default è che il confronto tra $row['id'] e $_POST['categoria'] sia sempre falso. Prova questo codice di debug:

Codice PHP:
$query mysql_query("SELECT * FROM categorie_gallery ORDER BY nome ASC");
$categoria = isset($_POST['categoria']) ? $_POST['categoria'] : '';

echo 
'<select name="categoria">';

while(
$row mysql_fetch_array($query)) {
    
$id $row['id'];
    
$nome $row['nome'];
    
$selezionato $categoria == $id 'selected="SELECTED" ' '';

    echo 
"<option value=\"$id\"$selezionato>$nome ('$categoria' == '$id')</option>";
}

echo 
'</select>'
Richiama la pagina e controlla fisicamente cosa c'è nelle parentesi: potresti avere delle sorprese...