On horde character, after completing most of bonfires in Eastern Kingdom, saw that bonfire in Vashj'ir is marked as done despite not going there (on that character, I haven't been to that region). Re-logging didn't seem to fix that.
Edit. Restarting WoW did fix it.