Esta questão já está um pouco antiga, mas no caso de outras pessoas se depararem com esta página (como eu fiz), aqui está o que me fez trabalhar:
No meu caso, a resposta foi aparente.
A solução:
edite o arquivo /etc/apparmor.d/usr.sbin.mysqld
Adicione as seguintes linhas:
/path/to/new/data/ r,
/path/to/new/data/** rwk,
/path/to/new/logs/ r,
/path/to/new/logs/ rw,
Em seguida, reinicie o apparmor:
sudo /etc/init.d/apparmor restart
O AppArmor está impedindo que o mysql acesse os novos locais para esses arquivos. É por isso que todas as permissões parecem corretas. É correto que "alguma coisa" esteja impedindo que o mysql acesse os novos locais. Essa "coisa" é "apparmor": -)
Apparmor parece ser padrão no Ubuntu 11.10, que é onde eu tive esse problema. 10.04 não parece ter o Apparmor instalado por padrão.
Espero que isso ajude alguém, eu tenho arrancado meu cabelo por causa de muitas horas!