So certainly in the UK there is this trope that the Rome fell in 476 CE and from then on the whole Roman world ended. There is essentially no common knowledge of the Eastern Empire and when there is its generally lumped in as Byzantine and not connected with the Romans at all.
At what time did this shift occur? I have read somewhere that Edward Gibbon was at least partly responsible but can't remember where. How did the contemporaries of the empire view it? Did the Arabs, Persians, Bulgarians etc see themselves fighting Roman armies or Byzantine ones? Did the Fourth Crusade think they had sacked a Roman city?
By Heironymous Wolfram, in 1557, 106 years after the Roman Empire fell.
It was never called the Byzantine Empire. Byzantine is a term used in the modern day to refer to the Roman Empire from 476-1453 AD, as the Roman Empire survived the collapse of the West. The terms usually used were along the lines of Rhomania (Roman-land which first appears in Latin in the 4th century AD), etc. for what they called their Empire. They called themselves Romans and continued to even after the end of the Empire in the 15th century. There are still Greeks in the Aegean, the mountains, and Anatolia that call themselves "Romans."
The debate about whether or not Byzantium can be considered the Roman Empire stems primarily from the changes from a Roman to Greek language, differences in culture, restructuring of the administration, and restructuring of the army. But these latter three weren't significant changes from late antiquity, and late antiquity was just as different from the Principate empire than the "Byzantine" empire was from late Rome. The argument is ongoing, but as a whole many historians are moving away from the term "Byzantine" empire and referring to it as it was - the Roman Empire. Although they usually distinguish it by calling it the Eastern Roman Empire.
Hopefully someone can elaborate more, but that is the short version.
See "Roman Identity in the Sixth Century" by Geoffrey Greatrex, "Roman Identity in Byzantium - A Critical Approach" by Ioannis Stouraitis
Anthony Kaldellis also discusses this extensively in his "Hellenism in Byzantium"