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 .emacs file 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.