A reboot on the new machine did get the shell menu back. However, my main machine that I've always used with MC doesn't get the menu back with a reboot. I haven't checked my computer at work which I also always use with MC but I know I have rebooted that a couple times last week and it still didn't have the menu. So it appears that computers that previously used older versions of MC have lost the menu.
EDIT: On all my computers, I use Directory Opus. On my main home machine right now, I opened Windows Explorer and the Media Center menu is there, but it isn't in Directory Opus. This is weird because the new machine is also using Directory Opus and the menu is there. For some reason, I'm not getting the same right-click menu between the two explorers on my main computer.