Qualche giorno fa ho avuto lo stesso problema su Debian dopo un dist-upgrade azzardato
Per risolvere ho dovuto commentare
codice:
#old_passwords	= 1
in my.cnf