Those scripts are ran from the initrd, so it’s looking for plymouth and plymouthd in the initrd /bin and /sbin directories, and those are probably missing the said files just as the error message says.

/usr/share/initramfs-tools/hooks/plymouth is responsible for copying the plymouth executables onto the initrd, so to see why it fails to copy the files, I added `set -x` to it and then ran `update-initramfs -v -u`.

In my case (I’m running Kodibuntu, I recently upgraded the underlying system from 14.04 to 16.04) the issue was that the hook failed to find Kodibuntu theme files for Plymouth, because it was looking for them in /usr/share/plymouth/themes (which apparently is the standard place), whereas the files actually resided in /lib/plymouth/themes for some (legacy?) reason. The hook therefore determined that I have no working Plymouth theme and thus don’t need the executables.

After moving the theme files to /usr/share/plymouth/themes (and some manual labor updating references in the files themselves as well as Plymouth’s alternatives) the hook now correctly finds those files and then proceeds to copy the Plymouth executables onto the initrd.