it does seem strange if it always happens that way... i think i have encountered a crash or 2 where i had to reboot, but definitely not every cs4 crash.
i'll give the obvious suggestion, make sure you have the latest update for cs4 (9.0.3).
the next time it happens, you might open the activity monitor (applications>utilities) and see i all ae processes have quit. it's possible that some of the processes are still running and that is preventing ae from relaunching.
with cs3, i remember ae crashes would often leave the aeselflink processes running (those are the background render engines that ae uses for multi-processing). relaunching cs3 would then open a new series of aeselflink processes, and performance would go way down, but it still launched... to get ae back to working properly i would have to use the activity monitor to quit each aeselflink manually, then relaunch ae (of course a reboot would do the same).