Удали пакеты которые плохо стали/их зависимости и попробуй так:
# aptitude update (лучше использовать aptitude вместо apt-get - лучше разрешает зависимости)
# aptitude upgrade (обновляем системные файлы/либы)
# aptitude install mysql-server