Even though in After Effects CS4 there's a new preference item to set how many cores to use (or how many to leave idle for other purposes), you have to bear in mind that this feature works by launching a number of background processes (ie, headless versions of the full application) according to the number of cores in your machine. Because of this, the more cores you have, the more RAM you need for the feature to work at all (or it will simply refuse to launch the background processes because of insufficient RAM). For a quad-core machine, 8 GB of RAM would be the minimum recommended amount (you could probably get all 4 processes to launch with 6 GB, but I don't think that would be a good idea). You should be able to have at least 2 cores used in your desktop system, though. Go to Preferences > Memory and Multiprocessing. Of course, enable "Render Multiple Frames Simulataneously" and make sure "CPUs to leave for other applications" is set to 0 (zero). Also, check that the minimum allocation (ie, minimum RAM amount per core for the processes to launch) is 0.5 GB.
If the number of cores is still 1, try moving the Longer RAM preview/Faster rendering slider and see if at some point, it enables the second core.
In the long run, upgrading your desktop system to 8 GB of RAM (or more, if the motherboard allows it) would be the best move.
Of course, for an in-depth description of all settings involved, take a look at the Memory & Multiprocessing preferences section in After Effects Help.
What are the exact processor models? And what operating system are you on? It's well within reason that if you run your quad with Win XP Home, the operating system limits the number of cores and their usage. Only XP Professional or Vista (any version) can handle multicore systems more efficiently. Do they correctly show up in task manager and can other programs use them properly (to test, run DXDiag and watch the task manager for instance or download a benchmark tool)? Barring that, definitely run a manual Windows Update. Use the Custom mode and on choosing additional software, include the .NET Runtime 1.1 This will update several system DLLs which may fix your problem - alll of course assuming, you are on the right operating system to begin with.