I think they had greenary, Grondy, it just wasn't growing. I always imagine the Sleep of Yavanna to be some sort of magical state in which the forests became frozen in time, fully grown and green, but totally dormant. The animals, too, were said to have slept through this period. As the Elves were not renowned for hacking down trees, I can see how this state could be maintained until the Second Spring of Arda. It does not explain what the Elves ate, however, unless there was plentiful bounty to start with. This later problem could explain why the Elves migrated West, though, moving on as their food became scarce. Tree cutting Dwarves would also be more of a problem too, as re-forestation would not be possible during this period.
Melian also managed to use her own powers to overcome the Sleep of Yavanna within the bounds of Doriath. In this case, I imagine the forests fed on Melian's power rather than photosynthesis for nourishment.
Interestingly, it is with the Second Spring of Arda, when everything is suddenly springing back to life, that Elves first to begin feeling weary within Middle Earth. After experiencing dormancy of the ancient forests, or the unchanging Undying Lands, this sudden rapid changing of the seasons must have come as a shock to the long-lived elves.