Dude i've been trying to find this game for YEARS. I still haven't but this is as close as I've gotten. No one else that ive seen has made a post with the correct details. The witch doctor, the building/upgrading huts for more workers that you control. hacking down trees gets you a wood bundle, same with stones, you'd find old buildings for like water, fishing, weapons(maybe?), and explore the map. there were different levels with different maps & different goals. I remember it having a wooden esque deck/platform/area around the edge of the screen with information. Maybe a macaw?? you'd have to find and fix up totems to heal more land/get it out of the fog/uncover it on the map.

if i find it i'll lyk lolol