A thousand years seems like a good amount of time for some pretty dense forest to regrow. Look at American east of the Appalachians: it was pretty much denuded, and now it's fairly large trees that have regrown in a hundred years or so. Mind you, there are a couple of critical species missing (the passenger pigeon, carolina parakeet, and American Chestnut) in that new forest and there's not telling how many less charismatic species disappeared. As I understand it, there are places where it's illegal to tear down old walls and you will frequently run across an old field wall in the middle of what is otherwise dense forest.

A similar regrowth place on the thousand-year scale is old Mayan empire. Evidence suggests that there wasn't a significant tree left standing by the time they were done (and that the deforestation may have been a significant factor in their decline). Now it's dense, tangled forest. Again, there no good way to tell what's been lost since the original old-growth forests.

The map looks good. Things seem plausible on the map, with the exception that there might be more forests than you have shown (if it's not cultivated, grassland, or wasteland, I would expect to see it forested).