Googling since two hours, I require your assistance. I'm on a Debian virtual machine and I cloned it. The only change is the new IP adress it has.

Mysql doesn't start any more:

Starting MySQL database server: mysqld . . . . . . . . . . . . . . failed!

There is no process called mysql. All the mysql log files in /var/log are empty.

here is my.cnf file :

[client]
port        = 3306
socket      = /var/run/mysqld/mysqld.sock
[mysqld_safe]
socket      = /var/run/mysqld/mysqld.sock
nice        = 0

[mysqld]
user        = mysql
pid-file    = /var/run/mysqld/mysqld.pid
socket      = /var/run/mysqld/mysqld.sock
port        = 3306
basedir     = /usr
datadir     = /var/lib/mysql
tmpdir      = /tmp
language    = /usr/share/mysql/english
skip-external-locking
bind-address        = 127.0.0.1
key_buffer      = 16M
max_allowed_packet  = 16M
thread_stack        = 192K
thread_cache_size       = 8
myisam-recover         = BACKUP
query_cache_limit   = 1M
query_cache_size        = 16M
general_log_file        = /var/log/mysql/mysql.log
log_bin         = /var/log/mysql/mysql-bin.log
expire_logs_days    = 10
max_binlog_size         = 100M

[mysqldump]
quick
quote-names
max_allowed_packet  = 16M
[mysql]
[isamchk]
key_buffer      = 16M
[mysqld_safe]
syslog

Here is the result of ifconfig :

eth0      Link encap:Ethernet  HWaddr 00:0c:29:12:98:9a  
          inet adr:192.168.1.138  Bcast:192.168.1.255  Masque:255.255.255.0
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:754 errors:0 dropped:0 overruns:0 frame:0
          TX packets:106 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 lg file transmission:1000 
          RX bytes:101177 (98.8 KiB)  TX bytes:17719 (17.3 KiB)

lo        Link encap:Boucle locale  
          inet adr:127.0.0.1  Masque:255.0.0.0
          adr inet6: ::1/128 Scope:Hôte
          UP LOOPBACK RUNNING  MTU:16436  Metric:1
          RX packets:8 errors:0 dropped:0 overruns:0 frame:0
          TX packets:8 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 lg file transmission:0 
          RX bytes:560 (560.0 B)  TX bytes:560 (560.0 B)

As requested, here is the result of : sudo -u mysql mysqld, here is the result :

root@debian:/home/nicolas/Bureau# sudo -u mysql mysqld
121004 14:26:57 [Note] Plugin 'FEDERATED' is disabled.
mysqld: Can't find file: './mysql/plugin.frm' (errno: 13)
121004 14:26:57 [ERROR] Can't open the mysql.plugin table. Please run mysql_upgrade to create it.
121004 14:26:57  InnoDB: Initializing buffer pool, size = 8.0M
121004 14:26:57  InnoDB: Completed initialization of buffer pool
121004 14:26:57  InnoDB: Started; log sequence number 0 70822697
121004 14:26:57 [Note] Recovering after a crash using /var/log/mysql/mysql-bin
121004 14:26:57 [Note] Starting crash recovery...
121004 14:26:57 [Note] Crash recovery finished.
121004 14:26:57 [ERROR] mysqld: Can't find file: './mysql/host.frm' (errno: 13)
121004 14:26:57 [ERROR] Fatal error: Can't open and lock privilege tables: Can't find file: './mysql/host.frm' (errno: 13)