Este error sucede en varias versiones de Ubuntu y con mysql-server-5.1 y mysql-server-5.5.

Al hacerlo con apt, regresa un error, también si lo intentamos con tasksel (E: Sub-process /usr/bin/dpkg returned an error code (1)).
La solución es simple, solo hay que hacer los siguientes pasos:

$ sudo apt-get remove mysql-server-5.1

$ sudo apt-get purge mysql-common

$ sudo apt-get purge mysql-server-5.1

$ sudo apt-get autoremove

$ sudo apt-get clean

$ sudo apt-get install mysql-common

$ sudo apt-get install mysql-server