I went for office stuff with company's driver the other day and asked him some questions about some areas in Bali. Here's what I got from him:

Batu Belig
Batu means rock. Belig is slippery. So it was told that the elders who first came to Bali was going for an isolated prayer and found a slippery rock surrounded by moss (belig) from which fire came out. He then made the area sacred and from then the place is called Batu Belig.

Petitenget
Came from the word "peti" (box) and "tenget" (mystical). Long time ago a priest who came to Bali put the mystical box in the temple in this area, with a genie named Bhuto Ijo to guard it. The priest then ask local people to build the temple in the area.

Kerobokan
Means "mass fighting" from word kerobok, because the people in this new village came here from a fight at their old place. The new village is believed to give them new peace after the messy fight.

Kuta
Once, Gajah Mada from Majapahit kingdom harbored in the southern of this area, named as kuta (fortress) for it became their harbor and fortress to conquer Bali. While the two other harbor spots are named from Javanese words, Tuban and Canggu.

Jimbaran
This area was named from the word jimbar which means "wide spread". Once son of the King of Klungkung was casted away and ended up in this area, using his magical power to heal local people and reunited with his brother here.

And here are more words that are commonly be a name of place or area in Bali:

Bendega or Menega : fisherman
Bendesa : groups of several Banjar
Banjar : groups of 250 families (sometimes it can be 600 families), which had been settled from long time ago.

I kinda forget what else did I learned, gotta post them later when I remember..