I had same problem on a server. Basicly the path had gotten overly long. I cleared out a bunch of junk entries that didn't need to exist and it started working.
I'd suggest copying your environment path variable data to something else, cut out anything possible and try again. I'd be willing to bet it works then.
Be sure in the cutting out that you leave perl and window system paths intact.
CleanPath will automatically strip out any invalid directories from your path (both for the current command shell and in the global configuration in the Registry -- though most other things won't notice these changes unless you log out or otherwise poke them to).
It doesn't fix directories that still exist but that shouldn't be in %PATH%, though.