This might happen because Emacs tries to look for the shell in a wrong
place. If you know where your shell executable is, set the variable
explicit-shell-file-name in your init file (see How do I set up an init file properly?) to point to its full file name.
Some people have trouble with Shell Mode on MS-Windows because of intrusive antivirus software; disabling the resident antivirus program solves the problems in those cases.