LOL. Small world. Just trying to do this myself. (Install Dune 2k on Win7 x64.) Same problem.
Solution I'm attempting now is downloading the game (a whole 64mb I believe) from a site that was linked on another thread on another site regarding this problem. I'd link here, but I'm sure there's rules against linking to potentially pirated copies.
Before I get insta-banned for even talking about it, happy to post a picture of my game CD. Or link to other thread.
That's my solution at the moment.
EDIT: Confirmed. I'm up and running. One solution has been the "Install on x86 system, copy all files to x64 system, fix registry." When I did the install, it looked like it was just unzipping an archive with all the relevant files (so basically, someone else did step 1 regarding the x86 system for me/others and packed them for easy unzip on x64 system). Don't know if it dropped the reg. keys that are needed, but the game does work.