I had this same problem on my brand new gaming computer with Windows 8... as it turned out, the game actually needed some older DLLs that were no longer included in the newest Direct X update. I found a pack online that contained a big group of DLLs older games require to play properly. I'm trying to find the link now, I'll post it here for you if I can find it. Someone also suggested installing a random older game on your computer, because those often include the older DLLs you need. Good luck.

Also, give the "run as administrator" thing a shot. You never know.