They are in the application folder.
C:\Program Files (x86)\Adobe\Adobe After Effects CS4\Support Files\Presets
This seems to be where not only the plugins want to put them, but also After Effects. When I go to save an Animation Preset is suggests I put them in that folder listed above. Have you had luck putting them in the Media Core folder? I see what Adobe is attempting to do with the Media Core folder (or at least I think I do), but it seems like they made a half-hearted attempt.
Don't install animation presets in the Media Core folder.
That folder is for plug-ins shared between Premiere Pro and After Effects. You should not even install plug-ins there unless you're using the same plug-in for After Effects and Premiere Pro.
In past versions I assume this was done while the program was opening? Does anyone know of a way to have animation presets load automatically.
Normally it would do that on launch, if the Effects&Presets palette is open. If the palette is not visible, it doesn't do it. It should not have anything to do with your problem, though. More likely you are falling victim to a language mishmash, so the question becomes in which language you installed the program and in what language you are using it. If you e.g. installed it in German, but launch it in English, some presets would not show up, 'cos they have localized effects references and expressiosn. This should however not affect not presets you created on your own (assuming you store them inside the AE Presets dir) or third-party presets like the Trapcode ones...