Company of Heroes required that a minimum of 768MB of Virtual Memory be allocated to the game to run. You can either set a minimum amount of 768, or set the system to let Windows manage it and the game will run.
Here's some steps for folks that don't know how to do this...
Go into your control panel and open the system applet (or hold the Windows Key and Hit Pause).
When system properties opens, go to the Advanced Tab.
In the Performance Box, hit the settings button.
On the settings screen, go to the Advanced Tab.
In the Virtual Memory box, click "Change".
On that screen either set your minimum memory amount to 768, or change it to allow windows to manage it.
OK all the way out, and you'll be good to go.