Oh my God... apologies to all! Complete user error. I'd been using some software from a laptop to reorganise my music collection folder structure, and hadn't refreshed the database. No wonder it couldn't find the files. Resynched the media, and whaddyaknow.
Thanks for all the suggestions. I still have the problem with foreign characters not being picked up properly, but most of my music plays. The NAS drive is still read-only for LMCE, and working fine.