That the scheme actually has a net positive effect, both in the short and long-term
How effective a tree planting scheme is in capturing and storing carbon dioxide, is for a large part determined by what happens to the trees after they are planted. When trees mature and are harvested for wood that's used in construction, then the captured carbon dioxide is stored for a long time (until the wood decomposes or is burned). However, if no trees are replanted after harvesting this will have had a one-time effect only. Also when wood is burned (for energy or in a wild fire), or if trees die quickly and decompose, then their captured carbon is released again. Of course all trees die eventually even when they are not harvested, this is part of the natural cycle, but a mature forest can store a lot more carbon than a young, newly-planted forest so it's important to keep a forest intact as much as possible.
That the wrong type(s) of trees are planted in the wrong location
In the past there were bad offsetting schemes that planted non-native trees, or planted trees in a location where they would change water flows and thus change local ecosystems in a negative way. Some offsetting schemes planted thousands of trees of the same species, resulting in a large monoculture. Such a monoculture hinders biodiversity, is susceptible to diseases and can even damage local communities. There have also been reports that planting trees above a certain latitude can have a net warming effect by changing the albedo and trapping heat.
That buying offsets reduces the incentive for people to reduce their emissions
Reducing emissions is much more effective than offsetting. Buying carbon offsets can lead to people thinking they are doing the right thing, whereas they had better spent their time and effort in reducing their emissions. Of course this point goes for all offsetting-schemes and is not specifically for planting trees.
That there are more effective ways of reducing carbon emissions than planting trees
Nowadays many offsetting schemes invest in development of renewable energy sources (in developing countries) instead of planting trees, simply because it is a more effective and cheaper way to reduce emissions.
Questions about tree planting have come up on StackExchange quite often, and in the news various countries have great drives to plant vast numbers of trees in a single day.
A common issue seems to be a misunderstanding of the relationship between planting 'a tree' and 'offsetting carbon'.
Whilst its true that a single mature twenty year old tree will both sequester around 3 tonnes of CO2 in its woody mass and also lock about 3 tonnes of CO2 into a cycle of growing leaves, dropping them and decomposition, so a total of 6 tonnes offset; in order to get a twenty year old tree its not as simple as planting one seedling.
This news article covers Turkey's attempt to plant 11 million trees in 2019, of which about 90% died. This article questions whether the fragile state of Ethiopia was able to plant a billion trees in one year.
From my own experience, in order to grow a healthy twenty year old tree, you need to plant about a dozen seedlings of various species, relatively close together, and over a twenty year period, you cultivate and care for them and occasionally cull them until one remains.
Can you simply say that to offset the 6 tonnes of CO2 with a mature tree you need to plant 12 seedlings, so each seedling is equivalent to offsetting half a tonne? Maybe, but that nuance is too much for most government policy headlines.
Another point to consider is that most trees drop a thousand or so seeds each year, many of them can germinate all by themselves without human interference. In the UK there are 3 billion trees, so that could be 3 trillion seeds dropped, even if only one seed per tree successfully germinated into a new seedling, that's still the tree population doubling every year. Planting seeds is easy.
The Damcon PL10 (with four row attachment) is a popular tree planting trailer for use on farms and plantations, and can plant around 20,000 seedlings in a single day. Planting seedlings is easy.
What's difficult, both practically and politically, is cultivating the new trees for twenty years. Its a lot of commitment. It takes land and funding and people, and at any moment a new government or local authority with different priorities could decide to rip up the new forest and build a freeway, or use the land for farming and all the effort of planting trees is gone in a puff of smoke (CO2).
One concern is that it takes too long. Because a sustainable forest needs decades to grow it is a midterm solution only.
Another concern that comes to mind which I have not yet heard is that the forests compete with farming over land use: Both need reasonably fertile land. This conflict resembles the one created by plants grown for fuel: Rich countries create a large-scale demand for land for non-food purposes, driving the value of land up until it is uneconomical to grow food on it. But fertile land is a limited resource which will be needed to feed a still-growing world population.