System Restore did not fix it.

Something strange though. I wanted to see if adding virtual drives would
help, and when I added one (virtual cd drive) the "explore" option for My
Computer disappeared... When I right click My Computer, I can only open it.
There's no option to explore it.

Pressing WinKey+E gives me a "The Parameter is incorrect" error box, and
explorer does not open... mmm. Hope this can be of help. Adding the regkey
entries in the link you provided earlier, gives back to option to "explore"
My Computer.