Various times after I had conquered a town from another European country nearby Natives' attitudes towards me went down because they now believed I had stolen their land. I have never stolen land from the Indians.
It is fine if the Indians want the land back that others had stolen from them. But you should have the option to pay or return the tiles in question.
As it stands you are forced to raze European cities or prepare for war with the Indians as well.

If you buy land from Indians, then they still later believe that you have stolen it from them if their culture is dominant in some tiles. It is similar than "Our close borders spark tensions". And if you had war with Indians and razed their camp and later build on it then they automatically declare war on you.

Is quick production of liberty bells a way to reduce their anger in such a case then?

I've not tried this but then they later give away their cities if you do it in your LB push. But I think you don't want to increase the REF.

First of all sorry for resurrecting this thread, but I have the same problem and I am absolutely unable to understand why there is such a serious bug in a Firaxis game about two years after release.
I burned down Jamestown and because of that my former ally Sitting Bull, who asked me to fight the English in the first place, suddenly declared war on me (-35 you stole our land, England had destroyed one of their villages). If this is a feature, I don't want to know what Sid and/or his associates were smoking at that time. I can't help myself, but so far there seem to be a lot of bad design choices in this game.

Is there by chance a community bugfix or does anybody know how this AI reaction can be avoided/modded?
Thanks in advance.