I don’t have CS4 installed anymore to test this, but what makes you think »Video Frames to Layers« should work there?
Are you sure it did at some point?
As C.Pfaffenbichler said - unless you are sure it actualyl did work at some point, I'd consider it somewhat of a premature conclusion that it should work in CS4 just because it works in the other versions. There's so many variables with video... Your description also sounds liek your CS4 isn't actually the Extended version, so this could easily explain the absence of the timeline...