mysql doesn't start after relocating data dir

Adding solution we came to in comments as a full answer for completeness...

Testing with su/sudo showed that while mysqld complained of permission errors, the mysql user could indeed successfully write to the folder, making it clear this was not a file system permission problem. (A useful first step if faced with a similar problem)

Some distributions of Linux (if not all?) now come with AppArmor which limits the files/folders that executables are allowed to access.

The solution in this case was to simply add the new path to the /etc/apparmor.d/usr.sbin.mysqld policy file.