There are three GameObjects on a scene ReproScene in attached project. Each object has unique name and the same tag.
(gameobject name -> tag)
"Dog" -> "Dog",
"Cat" -> "Cat",
"Sheep" -> "Sheep"

- go to "Tags&Layers" window
- there are 3 tags - delete second tag (it's "Cat")
- after deleting "Cat" got a tag "Sheep" and "Sheep" got a tag "Undefined"
(expected opposite, and "Untagged" instead "Undefined")

- go to "Tags&Layers" window again
- Exception thrown:
UnityException: Tag: Undefined is not defined.

Repro video http://screencast.com/t/ZIru4AmvUi62