Ubuntu has moved from Upstart to Systemd from version 15.04 and no longer respects the limits in /etc/security/limits.conf for system services. These limits now apply only to user sessions.
The limits for the MySQL service are defined in the Systemd configuration file, which you should copy from its default location into /etc/systemd and then edit the copy.
sudo cp /lib/systemd/system/mysql.service /etc/systemd/system/
sudo vim /etc/systemd/system/mysql.service # or your editor of choice
Add the following lines to the bottom of the file:
You could also set a numeric limit, eg LimitNOFILE=4096
Now reload the Systemd configuration with:
sudo systemctl daemon-reload
Restart MySQL and it should now obey the max_connections directive.