Not all MySQL processes are killed when restarting
Seems the issue for us was the use of the old-style /etc/init.d/mysql script, rather than the service mysql restart script provided by Upstart. We haven't had these issues when using the Upstart commands.