Had one like that three weeks ago. Booting in safe mode was also disabled.
These are getting pretty hard to clean out now.
I did the Ctrl-Alt-Del to bring up the process manager and stopped processes until "Can't run Programs" message didn't come up any more. Then I ran ComboFix and MalwareBytes.
Then I could boot in safe mode and ran ComboFix again letting it come back up in standard mode to do it's final clean-up.
Ran them both again in standard mode and cleaned up any junk I could see using Hijack This.
Then I installed AVG Antivirus and scanned again, but it didn't find anything.