Como você pode ler no Centro de Software, o mysql-server é um pacote vazio e depende da versão mais recente, que é determinada pelo mantenedor do MySQL. Então você pode tentar instalar a versão mais recente do mysql-server manualmente via
sudo apt-get install mysql-server-5.5
ou tente usar o Ubuntu Software Center. Em caso de dúvida, faça uma atualização e atualização do apt-get, só para ter certeza.
Se tudo isso não funcionar e se você não encontrar uma solução, você pode dar XAMPP a try, que é um pacote que inclui Apache, PHP e MySQL. Então você pode iniciar o servidor MySQL com uma pequena e agradável Interface Python clicando em "Iniciar".
Espero que isso ajude