Das ist kein Fehler oder Problem, sondern nur ein Standard-Check. Ein Problem gab es nur, falls danach Meldungen dieser Art auftauchen: "Table 'xyz' is marked as crashed and should be repaired"
Nein, das sollte extra stehen...
Mehr schreibt er aber nicht hin. 
Bei mir steht da auch nicht mehr wenn ich mysql neustarte. Liegt evtl am Loglevel.
Wenn keine Fehlermeldungen auftauchen und du danach zur Datenbank verbinden kannst, ist alles in Ordnung.
Zunächst handelt es sich bei der Meldung nur um den Hinweis, dass das System die Tabellen kontrolliert und auf Fehler prüft.
Die Wortwahl ist für uns Deutsche etwas missverständlich, beinhaltet aber keinerlei Fehlermeldung.
Die Meldung ist bei Debian eine Standardmeldung und muss erst beachtet werden, wenn wirklich Fehlermeldungen kommen.
Was phpmyadmin anbelangt!?
Hast Du mal in die Logs geschaut, was Dein Häuptling dazu sagt?
Ich könnte in den blauen Dunst raten!
- MYSQL mag bestimmte Sonderzeichen nicht, da hilft Maskierung oder nicht verwenden in Passwörtern
-- dadurch dann falsches Passwort
- falsches Passwort generell
- falscher Benutzername
- phpmyadmin ist nicht richtig konfiguriert
etc.
Alles Dinge, die Dir Deine Log-Dateien verraten können. 
Fehlermeldungen sind auch wichtig, um das Problem vielleicht einzugrenzen.
Gucke mal in netstat ob der mysql Server überhaupt auf eingehende Verbindungen wartet.
<wdk> [~] netstat -tulpen
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address Foreign Address State User Inode PID/Program name
tcp 0 0 0.0.0.0:3306 0.0.0.0:* LISTEN 104 2995 1860/mysqld
So ungefair sollte das aussehen.
Ansonsten kannst Du ja mal meinen MySQL Verbindungs Checker aus meiner Signatur schnappen. Einfach in einen beliebigen Webspace auf deinem Server schmeißen, die Verbindungsdaten eingeben und den Output (natürlich ohne Passwort) hier posten.