It could be that the bacterial life was less varied than now. Fewer starting points reduces the chance of a particular useful set of mutations coming together. The individual parts might have randomly occurred a great many times before they happened in one population.

Also the availability of other resources might have meant that even if eating the tree parts did develop earlier it just wasn't enough to be a key survival advantage, especially if initial “versions” of the process were inefficient. Perhaps what happening was in one strain it lost the ability to feed on the older sources but had the latent ability to consume the new ones, even if much less efficient, so switched and continued from there to quickly refine the process via further mutation. Changes in the availability of other components, which the trees themselves will have had a hand in, will have changed the balance but over a significant amount of time.

Furthermore, and perhaps more significantly the components of our plastics and how they hang together are not that novel, requiring less changes to come together in one individual or population to make consuming them practical.