I rolled out IE8 to a group of test users in our organisation overnight, and after logging in in the morning, several of the users reported the error
Userinit.exe error and explorer.exe error - iertutil.dll not found
After clicking OK, the PC just hangs with the background visible.
A few people are reporting this error in various forums, but "do a system restore" is not a good solution. We can easily roll back to IE6 by replacing the DLL, or by uninstalling IE8. We just need a flawless rollout!
We're on Windows XP Service Pack 3.
Edit: We deploy via SMS. Initially we had 2 machines with the error, but somebody made a mistake with the test package and it rolled out five nights in a row. By the end of the five nights, 4 more machines had developed the same issue.
A quick google of the error message took me to this site here that appears to have the same issue as you're describing. Does their solution help you?
They're not just doing a system restore, as some of what they're describing is pulling the file from another location and copying it to the correct location on the erroring PC.