Although the geography is obviously vast, a suitable generic answer may also be appropriate: when would the average person living in the former lands of Western Rome realize that the [Western] Roman Empire no longer existed?
I believe that people in the different areas felt the Roman Empire no longer existed at different times. However I would place the start of the answer at the defeat of Constantine III and his death in the summer of 411. It is believed that he pulled most of the Roman Legions out of Briton for his efforts to save Western Rome and become Emperor. Thus someone living in Briton would have felt the Roman Empire was going in early 407 during the pull out, officially on their own in 411. Between 407 and 411 Constantine III represented Roman authority in modern day France. A person there was experiencing the successful barbarian invasion from Dec 31, 406, which was never repelled but simply co-opted to support various Roman figure heads. Seeing barbarians with quite a different culture living in areas West of the Rhine surely would make the average person there wonder if the Roman Empire was still in control. Constantine III minted coins so the average person would still feel 'Roman' in modern day France I suspect, just nervous. The Vandals (barbarians) reached modern day Spain in 409 and settled there, thus bringing the same feelings.
Shortly after Constantine III died Jovinus revolted in France but Emperor Honorius convinced invading Goths to attack and kill Jovinus in 413. The Goths were then taken out by Emperor Honorius in 414 after they lost the support of the Visigoths. Honorius handed over the nucleus of land for the next empire to the Visigoths in a treaty in 418. The average person probably didn't know that was the beginning of the end of Western Rome at the time though. Just another deal to maintain the support of the most important barbarian group at the time.
The Franks, Visigoths and others ruled as legates of the Roman Empire from roughly that point until 475 when the Visigoths under Euric were granted full independence from Rome. Between 418 and 475 the barbarians took more and more control from a weakening Rome. People in this period likely came to understand that barbarian kings were the real power through France and Spain.
I didn't mention Italy as I feel people there likely felt the Roman Empire existed right up to the end...and beyond Odoacer taking Rome in 476. The Eastern Roman Empire still exerted influence in Italy long past 476.
When answering this question, it is important to remember that 476 was a 'manufactured turning point', a date that represented what (some of) the elite in Constantinople thought around 518, not what they thought decades earlier.^1 Moreover, I don't think it is possible to know what the 'average person' thought, only what sections of the elite wanted to portray themselves as; even so, the picture is much more complex than /u/NoelTrotsky's answer.
Some people did recognise that they were no longer directly ruled by the Roman emperor, the most obvious being Sidonius Apollinaris, for whom the empire did end in 476, for the office-granting centralised government that the Gallo-Roman aristocrat saw as the essense of empire had disappeared.^2 But that did not reflect everyone's opinion. This is essentially the only source we can point to for 476 being of any significance amongst contemporaries. One noble in Visigothic Gaul, that's it. Elsewhere, our sources are fragmentary. Roman control of Britain perhaps disappeared around 410 or much later, since we have no secure sources for that - the frequently cited date of 410 relies on Zosimus, an early sixth-century Greek historian who should not be trusted on an event so far away (not to mention the fact that the entire passage is difficult to interpret - was it even referring to Britain?). In Gaul, warlords dominated, but again it is difficult to clarify the situation - was there a Kingdom of Soissons, ruled by a Roman general? It's probably less clear than that, with the polity having a major Frankish element. Yet all these warlords would have used Roman titles, attempted to maintain the Roman administrative system, or otherwise relied on Romans to rule. The centralised government of the western empire fell, but not the Roman world.
More than that, coins from this period continued to be minted with the (eastern) emperor's image. Theoderic in Italy was possibly seen by his subjects as the head of a renewed Western Roman Empire, a man 'born for the good of the res publica' and the 'propagator of the Roman name'. In Gaul, the Burgundians sought imperial titles from Constantinople and Clovis of the Franks became a consul in 508, perhaps even declaring himself to be an Augustus. In North Africa, we know little about the Moors themselves, but two inscriptions are particularly striking:
Ego Masties dux ann(is) lxvii et imp(e)r(ator) annis x, qui nunquam periuravi, neque fide(m) fregi neque de Romanos neque de Mauros et in bella parui et in pace, et adversus facta mea sic mecu(m) Deus egit bene.
I, Masties, dux for 67 yeas and emperor for 10, never betrayed, nor broke the faith, neither with the Romans nor with the Moors, and I obeyed in war as in peace, and for that, by reason for my conduct, God gave his kindness to me.
The second:
For the health and safety of Masuna, king [rex] of the Moorish people and the Roman people. [This] stronghold was established by Masuna, built at Altava by Masgivin, prefect of Safar, and Iider, procurator of Castra Severiana, and finished by Maximus, procurator of Altava in the provincial year 468 [AD 508].
That there was a Moorish imperator and a king of Romans and Moors active in the late fifth century is intriguing enough, but they fit in well with what was going in the rest of western Europe. New rulers were in place, but it was not a dramatic change at the top - instead, 'barbarians' continued to act as Romans, just as they had done before '476', all hungering for Roman titles, using Roman coins, and collecting Roman laws. Nor was the east forgotten, per the New Cambridge Medieval History:
The beginning of the century saw Anastasius (491–518) on the imperial throne, ruling an empire that was still thought of as essentially the Roman Empire, coextensive with the world of the Mediterranean, however unrealistic such a view seems to modern historians, who have the benefit of hindsight. Although Anastasius ruled from Constantinople, ‘New Rome’, over what we call the ‘Eastern Empire’, the Western Empire having been carved up into the ‘barbarian kingdoms’, this perspective is ours, not theirs. Through the conferring of titles in the gift of the emperor, and the purchasing of alliances with the wealth of the Empire – wealth that was to dwarf the monetary resources of the West for centuries to come – the barbarian kings could be regarded as client kings, acknowledging the suzerainty of the emperor in New Rome, and indeed the barbarian kings were frequently happy to regard themselves in this light. The discontinuation of the series of emperors in the West, with the deposition of Romulus Augustulus in 476, was regarded by very few contemporaries as a significant event: the notion that East and West should each have its own emperor was barely of a century’s standing, and the reality of barbarian military power in the West, manipulated from Constantinople, continued, unaffected by the loss of an ‘emperor’ based in the West.
The western empire may have disappeared, but the Roman Empire itself did not and that continued to have a major influence on both in provinces directly ruled in Constantinople and in the 'post-Roman' west, where the empire was still a living breathing entity. It is impossible to know what the 'average' person though, but for those at the top of the hierarchy, their perspective would have been far more Roman that most people would have expected.