I was playing a game last night where Byzantine wasn't in its usual tile. (3000 BC start) It was one space to the left of the strait so that ships couldn't get into the black sea. What made this really interesting, however, was that when 1500 rolled around and I had conquered all of Greece, I still failed the UHV. Obviously this was frustrating, but in hindsight I should have just burned Byzantine and build Istanbul from scratch.

I'm just wondering if this is a glitch or if this is how that goal ought to work. I'm really OK either way, but since I thought it was an interesting situation, I wanted to put it forward to the other Rhye's players to see what they thought.

You should have razed it and found it again. Or restart, like I did. I also waited to settle until I had Byzantium, so it was the capital (and in the meantime civics switch, if i remember correctly)