This is by no means a fix, and I'd definitely want to know how to fix this if it was me too, but if you need a freebie fix to tide you over, try
TotalCommander. I use Resco Explorer as another poster mentioned, but that one's not free.
FYI, in case you do want to delete the shortcut in Windows\Start Menu\Programs to File Explorer, the actual shortcut points to ":MSFEXPLORE" and not to an actual EXE. However, I believe this just launches Windows\fexplore.exe. Try launching that program manually after you have something like TotalCommander installed, or see if you can add it to your applications list manually.