First, check if you still have a Recycle Bin. Press Windows + E, go to the address, type "Recycle Bin", then press Enter.
Second, try restoring to an even earlier point; sounds like something screwed around with your registry. What programs did you recently install?