If you are running Vista, make sure that the Research in Motion directory has correct read/write/execute permissions. It's always the case when we install a new JDE or a new simulator in Vista, that this occurs; where half the things load, such as the JDE, and other things don't, such as the MDS and ESS, and the problem is, more often than not, that the directory settings are not appropriate. We typically just nuke that entire directory by changing the owner of the Research in Motion dir and subdirs to current user and setting everything in there to allow read/write/execute for current user. RIM installations simply don't play nice with the new Vista user access thing.
Aside from that, we have had occurrences where Java 1.6 simply did not work with MDS and ESS (especially the older 4.1.2 installation of the MDS/ESS package. If the permissions thing above doesn't work, try changing the active Java installation (the path to java.exe, essentially) to some version of Java 1.5.
Also, just re-reading your question, you should have a PATH variable in system variables pointing to the bin directory of your java JRE and java JDK installation -- that's where the executables live, and the MDS simply calls java.exe with its parameters, so the path needs to be set properly (and permissions on that dir need to be appropriate).