dík, dá se říct, že to nakonec pomohlo, konrétně:
- podle návodu se nepodařilo zastavit službu mysql
- po příkazu
mysqld_safe --skip-grant-tables se mi vypsalo chybové hlášení o tom, že je třeba ručně smazat dva soubory ve /var/lib/mysql (jediné dva co tam byly), to jsem udělal
- poté již šlo mysql službu zastavit, ale nešlo ji znovu spustit, a to ani po reinstallu mysql-server
- v synapticu jsem tedy kompletně odinstaloval mysql-common, mysql-client a mysql-server a pro jistotu jsem to restartoval
- po restartu jsem znovu nainstaloval zmíněné balíčky a všechno funguje jak má, nastavil jsem si nové heslo na roota atd.., sice jsem přišel o data, ale mám je zálohované
- PS: při uninstallu se mi navíc odinstaloval amarok a php5-mysql tak je nutné s tím počítat, že se to stane
