Nach einem Distributions Update von Debian Lenny 5.0 auf Debian Squeeze 6.0 kann es (mit sehr hoher Wahrscheinlichkeit) passieren das mysqld, der mySQL Server nicht aktualisiert wird und oder nicht startet.
In meinem Fall wurde das Paket mysql-server zurückgehalten und bei #apt-get dist-upgrade nicht mit aktualisiert.

Um die neue mySQL Version 5.1 nach dem Upgrade zu installieren den folgenden Befehl verwenden:

# apt-get install mysql-server-5.1

Ihr werdet unter Umständen feststellen das die Installationen soweit alle durchlaufen, nach dem Restart Versuch aber mysqld nicht neu startet. In dem Fall ist es vermutlich so das in eurer my.cnf der Parameter skip-bdb gesetzt ist. Dieser ist in der neuen Version 5.1 nicht mehr benutzbar und muss deshalb entfernt, bzw. auskommentiert werden:

# Using BerkeleyDB is now discouraged as its support will cease in 5.1.12.
#skip-bdb

Danach # apt-get install mysql-server-5.1 noch einmal laufen lassen und alles wird gut!