I had this problem... I cut around the reboot and got into explorer and hit the "Set Explorer as shell" shortcut.

I think the reason is that it prompts you to fix links and make sure the stuff is pointed in the right place.