|Sources: Lands of Mystery, 99-100|
Icemist Village is the former capital of the taunka (aka "winter tauren"). It is said that the village was originally an Icemist tauren outpost (but it is unclear how long ago that was), but is now the ravaged capital of the "winter tauren". It is located on the edge of Lake Wintergrasp within the Dragonblight. It was destroyed by undead nerubians and is currently controlled by the Scourge forces out of Azjol Nerub (which for some reason the village was built right next to). The Scourge here are led by Under-King Anub'et'kan whom players must kill during the  quest chain.
BackgroundThis section concerns content exclusive to the Warcraft RPG, and thus unlikely to be canon.
Tauren who moved to the Dragonblight lived only in one place, Icemist Village. Icemist Village was once a small village perched on the edge of Lake Wintergrasp. A pack of Icemist tauren settled on the west edge of the Dragonblight, on the shore of Lake Wintergrasp. They didn't venture into the blight proper very often, preferring the clean cold of the lake to the bitter air of doom and death of the blight. Icemist Village was a pleasant outpost, with friendly and helpful tauren. Most travelers in Northrend stopped there when passing in its direction. Travelers could always find someone with whom to trade or share information over a drink.
The tauren kept a ready supply of food, drink, clothes, and basic tools, and sold them to anyone who was in need. They even gave things away, if people were desperate, and they even dragged in travelers they found collapsed on the lake or in the surrounding area. Tundra Coldhoof oversaw the village.
The village became the capital of the winter tauren, the taunka. In time they spread out from Lake Wintergrasp and built villages elsewhere in Northrend, including in the Borean Tundra, Grizzly Hills, and Howling Fjord. The taunka high chief, Roanauk Icemist, has become Icemist Village's most recent ruler. Recently, the village was attacked by the Scourge and brought into ruin. Many of the taunka were able to escape and were held in protective custody at the Westwind Refugee Camp on the western border of the Dragonblight. Roanauk Icemist, however, was captured and remains in the ruins of the village.
Icemist tauren? Winter tauren? Taunka?
It is known that taunka originally were an offshoot of the tauren. It is unclear when they first became taunka however.
The terms "Icemist tauren" and "winter tauren" may be synonmous in meaning. This would make the term "taunka" synonmous as well. Several quests refer to the taunka as "winter tauren". Some quests use the terms "taunka" and "winter tauren" within the same quest, which shows that the terms are apparently synonmous and can be used interchangeably. See for example. If this is true, then maybe the "Icemist tauren" / "winter tauren" were always taunka, but have alternate race names (or that they first colonized the village when they were tauren and later became taunka).
Considering the new backstory (or expanded backstory), it is possible that Tundra Coldhoof is a taunka. Another possibility, considering there is a different leader replacing Tundra Coldhoof, is that the village once had tauren and taunka at the same time (although "winter tauren" and "Icemist tauren" may mean the same thing).
Another thing to consider is that material described in Lands of Mystery took place approximately 2-3 years before Wrath of the Lich King, which would have given time for certain changes in leadership and for the village to change hands. It may be possible that the "Icemist tauren" have evolved into taunka in the last couple of years.
Another good question to ask is "when" was the settlement first founded? It may have been founded as a tauren outpost a long time ago, but later became the taunka capital.