Eu tive esse mesmo problema TODA vez que eu tentei:
Selecting previously deselected package mysql-server-core-5.1.
(Reading database ... 242369 files and directories currently installed.)
Unpacking mysql-server-core-5.1 (from .../mysql-server-core-5.1_5.1.41- 3ubuntu12.10_i386.deb) ...
Selecting previously deselected package mysql-server-5.1.
Unpacking mysql-server-5.1 (from .../mysql-server-5.1_5.1.41-3ubuntu12.10_i386.deb) ...
Selecting previously deselected package libhtml-template-perl.
Unpacking libhtml-template-perl (from .../libhtml-template-perl_2.9-1_all.deb) ...
Selecting previously deselected package mysql-server.
Unpacking mysql-server (from .../mysql-server_5.1.41-3ubuntu12.10_all.deb) ...
Processing triggers for man-db ...
Processing triggers for ureadahead ...
ureadahead will be reprofiled on next reboot
Setting up mysql-server-core-5.1 (5.1.41-3ubuntu12.10) ...
Setting up mysql-server-5.1 (5.1.41-3ubuntu12.10) ...
E isso simplesmente fica pendurado. Desta vez eu deixei durante a noite, 12 horas depois, ainda está lá.
O que estou perdendo?
Parece que ele pode estar falhando quando deveria estar solicitando uma senha root do mysql. Experimente
export DEBIAN_FRONTEND=noninteractive
apt-get -q -y install mysql-server-5.1
Em seguida, defina a senha do mysql root depois usando
mysqladmin -u root password NEWPASSWORD
Um post que encontrei tocado na instalação do mysql é