[jfengel]

Some places naturally have water high in fluoride, due to the nature of the rocks and the water table.

That's how fluoride protection of teeth was discovered in the first place. People living in some parts of Colorado had mottled teeth from too much fluoride in the water. (It's now called "fluorosis".) Dentists noticed that such people also didn't get many cavities, and eventually tracked it to the composition of the water.

Turns out you can add enough fluoride to protect teeth without causing stains. Some places have way too much fluoride in the water. The staining appears to be the only problem.