Qual foi o comando que você usou para instalá-lo? Eu tentei:
sudo apt install mysql-server
e funcionou bem, no entanto, quando tentei:
sudo apt install mysql-server-core
deu-me a resposta
E: Unable to locate package mysql-server-core
Experimente o primeiro comando e veja se isso funciona.