Grab ccleaner and run the file cleaner then run the registry cleaner multiple times till it finds no errors.
What antivirus are you using?
Already tried CCleaner, it didn't find anything more than a missing .dll file or something and some uninstaller files.
I have Microsoft Security Essentials and Malwarebytes.
Turns out it was running a scan which I believe was the cause for my computer slowing down, but that still doesn't explain that Windows couldn't fix everything in the startup repair (which was due to a power outage I think, it may have been doing a windows update at the time).