Ordinary file-permissions are apparently not sufficient anymore. Ubuntu, and others, therefore uses AppArmor to associate programs with certain permission filters.
One such program is MySQL. When changing the datadir, it will most likely land somewhere outside the permissions granted by AppArmor and as a result fail. I would get errors (from /var/log/syslog) of the form:
Jan 19 00:41:12 asjo kernel: [262573.788599] type=1503 audit(1232322072.553:28): operation="inode_permission" requested_mask="r::" denied_mask="r::" fsuid=116 name="/vol/mysql/" pid=18262 profile="/usr/sbin/mysqld"
Others were having similar problems, as described in this thread among others.
This page solved my problem. Basically, you first put AppArmor in complain-mode regarding the specific program (in this case /usr/sbin/mysqld) by running this command:
sudo aa-complain /usr/sbin/mysqld
This will temporarily turn off the security and log the offending actions. Generate the offending actions by running the program:
sudo /etc/init.d/mysql start
Next you run
sudo aa-logprof
When asked if I wanted to “enable access to the profile repository” I answered L for ‘later’. Next it displays the offending action previously logged, at which point a allow it by answering A. At this point I am asked if I would like to save the changes. S for yes (save).
In order to re-enable security you simply run:
sudo aa-enforce /usr/sbin/mysqld
Aslak Johansen's Weblog 