La solución, en principio temporal y a medias, es editar el archivo /etc/init.d/mysql añadiendo a principio del script (después de la zona comentada) lo siguiente:
export LANG=es_ES.ISO-8859-1
export LC_ALL=es_ES.ISO-8859-1
Aviso: No queda resuelto el problema pues sigue apareciendo el error al iniciar mysql desde consola