MySQL kann wohl kein Verzeichnis tmp in /var/lib/mysql anlegen.
Mögliche Ursachen:
- keine Zugriffsrechte (was aber, soweit ich weiß eher errno 13 entsprechen würde (Erfahrungen mit Apache und falschen Zugriffsrechten)

)
- Dateisystem voll (auch wenn es eher unwahrscheinlich ist)
Die Ausgabe von 'ls -la /var/lib/mysql' sollte das mit den Zugriffsrechten klären können und ein 'df -h' das mit dem vollen Dateisystem ...
Zumindest wären das meine nächsten Schritte, nachdem ich die Logeinträgen gesehen habe.
Hast du was an der mysql Server Konfig geändert ( "... ich hatte vorher schon Probleme ...")?