I recently came across this issue on a client's PC. In this specific case the machine would randomly restart without any warning, and attempting to run Autochk at startup would fail with the same "Autochk cannot run due to an error caused by a recently installed software package" error.
Once the option to automatically restart following a crash was disabled it became clear that a file called HMFAxCoreXXXXXXXXXXXXXXX.sys was causing the system halt. Googling this file revealed it to be a component of the Hide My Folders application. The application itself could not be removed via the usual add and remove programs function - it looked like someone else had made a hamfisted attempt at removing it, breaking it in the process.
Renaming HMFAxCoreXXXXXXXXXXXXXXX.sys then restarting the system instantly fixed the unexpected restarts and restored Autochk functionality at startup.
Obviously this is an old thread but hopefully this may be of use to someone in a similar situation.