Some of the files that the error logs showed as missing did indeed exist and others did not. I would expect many files to not exist since we reused the database but not the moodle data directory.
I think I have tracked this down to the get_file_preview function in /lib/file_storage.php and the readfile function in /lib/filestorage/filesystem.php. It seems that if icons have moved (which they have because it is a new version of moodle and a new version of our theme) the hash doesn't differ and moodle doesn't regenerate a preview icon. It was the missing file icons themselves that were missing, but the files were being uploaded. This seemed to confuse moodle (and me) by showing broken information in the file upload widget. I have deleted the rows in the database for these missing icons and now things are working a lot better.
I wonder if this should be submitted as some kind of bug.
I think I have tracked this down to the get_file_preview function in /lib/file_storage.php and the readfile function in /lib/filestorage/filesystem.php. It seems that if icons have moved (which they have because it is a new version of moodle and a new version of our theme) the hash doesn't differ and moodle doesn't regenerate a preview icon. It was the missing file icons themselves that were missing, but the files were being uploaded. This seemed to confuse moodle (and me) by showing broken information in the file upload widget. I have deleted the rows in the database for these missing icons and now things are working a lot better.
I wonder if this should be submitted as some kind of bug.