Well if they have gardened there since the 80's, they very well could have had rights. Probably did, from the looks of the way it was handled. The city approved the project and then bulldozed it over within a week or so, in the middle of the night, right during the busy holiday season. That was so that no one would have time to get an attorney or fight it or try to assert any rights they had.
Then the bad guys said, oh well you were here illegally anyway. That is strange that since 198-s that tid bit didn't seem to matter and the land was widely accepted by the community as the Community Garden. All of the sudden when someone else wanted it, they started trying to dig up reasons to take it. I bet there was a pay off somewhere because the article says the city voted against it in Sep and that the community board also did not approve the new building.
Makes no difference who had rights to what, this whole situation was handled very badly.