Paid or trial?
Paid, and 4.2.
Yeah, you should have the presets.
Question: what was your install and update path?
The reason that I ask is that there have been some instances of an upgraded CS4 "reverting" to trial with an update.
That would be about the only thing that I could think of for the loss of the Presets. Do other things, MPEG, work?