Anebo prostě mysql -udebian-sys-maint -p*heslo*
*heslo* je položka password v souboru /etc/mysql/debian.cnf (automaticky generované při instalaci MySQL), Root po instalaci MySQL serveru v Debianu má přístup bez hesla (myslím, že má přístup bez hesla i v Ubuntu, ale nejsem si jistý.)
Po lognutí změnit heslo roota normálním způsobem. Na uživatele debian-sys-maint by se mělo dát lognout i přes PHPMyAdmina.
Jinak opravdu opakovaná reinstallace nikam nevede.