Em situações como esta, você precisa colocar os pacotes "não serão instalados" na lista principal de instalação.
Use o seguinte comando:
sudo apt-get install mysql-server libapache2-mod-auth-mysql php5-mysql libmysqlclient18 mysql-server-5.5 perl-modules