Feel free to stop replying at any point since I can't really help, but I can't see a reason why /usr/bin/ksplashqml itself would have gone missing.

Is it possible that ksplashqml was really present, and actually the "not found" error was because ksplashqml could not find a custom splash theme file? Had you installed and removed any custom themes?