I upgraded to 12.04 and my MySQL server just stopped working. It throws:

ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (2)

I tried to reinstall it from software center, but it fails with:

Package operation failed

The installation or removal of a software package failed.

installArchives() failed: Selecting previously unselected package mysql-server.
(Reading database ... 
(Reading database ... 5%
(Reading database ... 10%
(Reading database ... 15%
(Reading database ... 20%
(Reading database ... 25%
(Reading database ... 30%
(Reading database ... 35%
(Reading database ... 40%
(Reading database ... 45%
(Reading database ... 50%
(Reading database ... 55%
(Reading database ... 60%
(Reading database ... 65%
(Reading database ... 70%
(Reading database ... 75%
(Reading database ... 80%
(Reading database ... 85%
(Reading database ... 90%
(Reading database ... 95%
(Reading database ... 100%
(Reading database ... 243412 files and directories currently installed.)
Unpacking mysql-server (from .../mysql-server_5.5.22-0ubuntu1_all.deb) ...
Setting up mysql-server-5.5 (5.5.22-0ubuntu1) ...
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
No apport report written because MaxReports is reached already
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.5; however:
  Package mysql-server-5.5 is not configured yet.
dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
No apport report written because MaxReports is reached already
Errors were encountered while processing:
 mysql-server-5.5
 mysql-server
Error in function: 
Setting up mysql-server-5.5 (5.5.22-0ubuntu1) ...
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.5; however:
  Package mysql-server-5.5 is not configured yet.
dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured

I also tried:

$ sudo apt-get install -f
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages were automatically installed and are no longer required:
  mysql-server-5.5 mysql-server-core-5.5
Use 'apt-get autoremove' to remove them.
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Setting up mysql-server-5.5 (5.5.22-0ubuntu1) ...
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
 mysql-server-5.5
E: Sub-process /usr/bin/dpkg returned an error code (1)

Any idea?

EDIT:

Crash report is being auto generated.

EDIT:

After trying and trying I got suggestion to do:

#apt-get --purge remove mysql-server-5.1 mysql-server-5.5
Reading package lists... Done
Building dependency tree
Reading state information... Done
Virtual packages like 'mysql-server-5.1' can't be removed
The following packages will be REMOVED:
  mysql-server-5.5*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 31.3 MB disk space will be freed.
Do you want to continue [Y/n]? Y
(Reading database ... 243407 files and directories currently installed.)
Removing mysql-server-5.5 ...
Purging configuration files for mysql-server-5.5 ...
Processing triggers for ureadahead ...
Processing triggers for man-db ...

The most important part is:

Virtual packages like 'mysql-server-5.1' can't be removed

Any idea?