Hm, tak zkus obnovit ty konfiguraky v /etc/mysql (ktere sis jestli jsem dobře pochopil zazalohoval), chown -R mysql:mysql /etc/mysql, obnovit obsah /var/lib/mysql, chown -R mysql:mysql /var/lib/mysql a pokud heslo debian-sys-maint v /etc/mysql/debian.cf je stejne jako heslo toho uzivatele v tabulce mysql.user, tak by to mělo jít. Pokud není, tak to vypíše tu chybu co na začátku.
Pak bys musel buď zjistit to heslo z dat té tabulky mysql.user a upravit ho v /etc/mysqldebian.cf anebo naopak upravit to heslo v tabulce podle toho debian.cf.
Je ale divné, že ti to po apt-get purge mysql-server a znovu nainstalování nevytvořilo znovu configy, dávals opravdu purge a ne jenom remove?