Just in case you're still having issues and still want to play the game - I've found that the issue is caused by the (what else?) Windows Game Explorer service, which frequently causes failures to run or other issues for old games.
The solution is simple, but a bit annoying. It's basically impossible to prevent Game Explorer from running permanently, but you can try starting the game from a frontend such as DxWnd, or do what I did.
I use a program called Process Explorer as a substitute to the regular Task Manager.
With this program, you can clearly see the rundll32.exe process that runs with the game, identified as the game explorer service.
Simply right-click that process, and click Suspend. The process will halt, but still register as running. Now kill the game process itself (it's prevented from working right by the glitched Game Explorer), and restart it. Since Game Explorer is registered as running already, it will not run again, and the game will continue running normally.
This works for all games that are often affected by failures to start and similar issues, like (in my case) Carmageddon II, Homeworld Emergence, Unreal Gold, and Total Annihilation.