Actually, running in compatibility mode works. Right click on the exe, click on properties, go to compatibility, select the "run in compatibility for windows 7" option in the drop down menu, then click apply. Then from then on, it should run fine.
I also have this problem for Half Life: Blue Shift on Windows 7, exactly as Inuplaya described. I can confirm with 100% certainty that I do have enough memory by far at the time of trying to run the game but the same message comes up. Please help.