Após alguma confusão geral sobre permissões, o OP percebeu que o problema não era que ele não tinha permissões e direitos de caminho, mas que o AppArmor estava impedindo o MySQL de ler e gravar no novo local.
Esta é a solução dele:
Primeiro, pare o MySQL para que nada de estranho aconteça enquanto você está mexendo:
$ sudo stop mysql
Em seguida, mova todos os diretórios do banco de dados para sua nova casa:
$ sudo mv /var/lib/mysql/<all folders> /new-mysql-dir/
Não mova os arquivos, eles serão gerados pelo mysql, apenas mova as pastas (que são os bancos de dados).
Então, educadamente, peça ao AppArmor para permitir que o mysql use a nova pasta:
$ sudo vim /etc/apparmor.d/usr.sbin.mysqld
>> add lines
/new-mysql-dir/ r,
/new-mysql-dir/** rwk,
Em seguida, diga ao mysql que o datadir foi movido:
$ sudo vim /etc/mysql/my.cnf
>> change the line
datadir=/var/lib/mysql
>> to
datadir=/my-new-db-dir/
NOTA: Dependendo da configuração do banco de dados, talvez seja necessário alterar também innodb-data-home-dir etc.
Em seguida, reinicie o AppArmor para ler as novas configurações:
$ sudo /etc/init.d/apparmor restart
E inicie o MySQL novamente usando o novo datadir:
$ sudo start mysql