Carry on with the rest of the instructions
In Safe mode instead of using Windows CleanUp!
Go to start>>run>>type in cleanmgr
Hit OK
Let it finish the scan and ensure temp and temp internet files are checked
We'll deal with cleanup later
Also in Internet Explorer
Under the General tab
Delete files + Offline content
Clear History and Cookies