Verifique seu log de erros do mysql.
tail -100 /var/log/mysql/error.log
Se o seu log diz (como o meu fez):
InnoDB: Initializing buffer pool, size = 128.0M
InnoDB: mmap(137363456 bytes) failed; errno 12
[ERROR] InnoDB: Cannot allocate memory for the buffer pool
Você não tem memória suficiente para usar o tamanho padrão do buffer de 128M
Edite o arquivo de configuração /etc/mysql/my.cnf adicionando uma linha para especificar um innodb_buffer_pool_size menor.
# make the buffer pool smaller than 128M since we only have 1 GB of total RAM
innodb_buffer_pool_size = 16M
Salve o arquivo de configuração e inicie o mysql
sudo service mysql start