OK, it appears to be working now. Big thank you to Thom for helping me understand the ins and outs and ultimately solve the problem.
Initially I set up a username/password on the NAS, and in the permissions settings for the share, selected the "only this user" option. That gave me the permissions problem across the whole NAS. A chmod -R 777 temporarily sorted it, except for the livetv folder (it would appear that myth was doing something to this folder after a reset). Interestingly(!), if I tried the chmod command again, permission was denied on this livetv folder.
So based on the advice on this thread, I tried with no username and no password on the NAS, and selected the "all users" for the permissions, and again no joy, some problem, but didn't have the same permissions problem when I tried to reapply the chmod command. Still no good though obviously.
After seeing some strange things with how the NAS was being mounted (strangely it had a "guest" username, plus a few other oddities permissions-wise), we tried to add a user "guest" to the NAS with no password, but the NAS wouldn't allow that. So we tried setting another arbitrary username/password as before, but this time I selected "all users" for the permissions, and it worked, even after a reset. No good from a security point of view (anybody on the internal network could access the NAS), but at this point I didn't give two poops.
What is really strange (I discovered this after I had left IRC), is that I changed the permission setting on the NAS back to the "only this user" setting, just to convince myself what the problem was, and it still bloody works LOL, even after several resets of both the core and NAS. I promise that I didn't do anything extra/different (I keep a meticulous log whenever I do anything with LMCE), and for some reason it still works as it should, which is good of course, but puzzling.
Still reading? Apologies for the saga, but I just wanted to get it all down somewhere in case somebody else has a similar problem. I'm not convinced these issues are unique to this NAS, because I had similar problems with a Netgear Stora that got sent back, but obviously I didn't look into the problems with that NAS in as much depth.
Cheers,
Matt.