ужасный путь, но попытка это:
sudo bash
# at this point take backup of your /etc/mysql and /var/lib/mysql
apt-get remove --purge mysql-server mysql-server-5.0
# if above fails
rm -rf /etc/mysql
echo "exit 0" > /etc/init.d/mysql
# and again
apt-get remove --purge mysql-server mysql-server-5.0
# and try from scratch:
apt-get install mysql-server-5.0