When you click MS-DOS you actually launch a PIF file, some kind of a shortcut. Have you tried Start|Run|Command ? If that functions fine, probably the PIF file is corrupt. It should be located in C:\Windows\Start Menu\Programs. You can safely delete it and create another one, just like you create a shortcut. As soon as Windows recognises it is referring to a DOS application (it should point to C:\WINDOWS\COMMAND.COM or C:\COMMAND.COM) it creates a *.PIF file in stead of a *.LNK file.
By the way, the COMMAND.COM file this PIF is referring to has not been replaced or so? Is it the same version as the one your PC boots from?
Jim