Windows 7 File Restore Fails with Path not found

When I try to restore data that was backed up with the built-in Windows 7 backup tool I get the error The system cannot find the path specified. (0x80070003). This happens only when restoring data - the backup process itself runs perfectly fine.

I tried completely removing the backup files and creating a new backup, but to no avail. Also the files are fine - at least I can access the backup directly and access files directly in it. Also the backup used to work when I tested it the last time.

Okay so the only way to resolve this was to fix the windows install itself. Will remain a mystery it seems..