Com a ajuda do Dominik acima, descobri que o Ubuntu está executando o apparmor. Cito da wikipedia:
AppArmor allows the system administrator to associate with each program a security profile that restricts the capabilities of that program
De fato, entre esses programas estava o mysqld. Portanto, não o usuário foi o problema, mas as restrições impostas ao processo pelo apparmor. Então eu encontrei a solução aqui
sudo touch /etc/apparmod.d/disable/usr.sbin.mysqld
sudo /etc/init.d/apparmor reload
Isso faz do mysqld um processo livre que, para mim, nesse servidor, não é problema. Então, depois de dias de busca, o problema foi corrigido!