O Ubuntu mudou de Upstart para Systemd na versão 15.04 e não respeita mais os limites em /etc/security/limits.conf para serviços do sistema. Esses limites agora se aplicam apenas às sessões do usuário.
Os limites para o serviço MySQL são definidos no arquivo de configuração do Systemd, que você deve copiar de seu local padrão para /etc/systemd e depois editar a cópia.
sudo cp /lib/systemd/system/mysql.service /etc/systemd/system/
sudo vim /etc/systemd/system/mysql.service # or your editor of choice
Adicione as seguintes linhas na parte inferior do arquivo:
LimitNOFILE=infinity
LimitMEMLOCK=infinity
Você também pode definir um limite numérico, por exemplo,
LimitNOFILE=4510 . Agora recarregue a configuração do Systemd com:
sudo systemctl daemon-reload
Reinicie o MySQL e agora deve obedecer a diretiva max_connections.
Eu também tive problemas para parar o MySQL de forma limpa após a atualização para 15.04. Se isso afetar você (você saberá porque levará 300 segundos para expirar quando você fizer
service mysql stop ou service mysql restart ) adicionando a seguinte linha ao mesmo arquivo /etc/systemd/system/mysql.service corrigiu para mim:ExecStop=/usr/bin/mysqladmin --defaults-file=/etc/mysql/debian.cnf shutdown
Este último problema parece ter sido corrigido por 16.04 e esta linha não é mais necessária, então antes de fazer uma atualização de distribuição você vai querer parar o MySQL e remover o
ExecStop linha do arquivo de configuração. 
