As I understand the issue, it's not within the power of the local tribes to prohibit visitors climbing. They express their wish that you do not, which is as far as they can go under the terms by which the rock was handed back to indigenous control.
From Wikipedia:
The local Aṉangu do not climb Uluru because of its great spiritual significance. They request that visitors do not climb the rock, partly due to the path crossing a sacred traditional Dreamtime track, and also due to a sense of responsibility for the safety of visitors. The visitors guide says "the climb is not prohibited, but we prefer that, as a guest on Aṉangu land, you will choose to respect our law and culture by not climbing."[4]
On 11 December 1983, Prime Minister Bob Hawke promised to hand back the land title to the Aṉangu traditional owners and agreed to the community's 10-point plan which included forbidding the climbing of Uluru. However, the government set access to climb Uluru and a 99-year lease, instead of the previously agreed upon 50-year lease, as conditions before the title was officially given back to the Aṉangu.[22]