Molto probabilmente esistono modi migliori, ma potresti fare...

...supponiamo che hai la stringa con i dati del nuovo utente nella variabile $lastUser:

1. metti il contenuto xml in una stringa
Codice PHP:
$testoContenutoNelFile = file_get_contents("nomeFile.xml"); 
2. sostituisci nella stringa ad "</utenti>" la parte relativa al nuovo utente postponendo "</utenti>"
Codice PHP:
$testoContenutoNelFile = str_replace("</utenti>", $lastUser."</utenti>", $testoContenutoNelFile); 
3. riscrivi l'intero file

Molto probabilmente già lo sai, ma l'xml non è un granchè per fare certe cose.

Infine dai un'occhiata qui

Se lavori con php5 magari simpleXML è quello che fa per te... magari, ma non ho la più pallida idea di cosa sia

Buona fortuna.