This conundrum has led to some people re-examining the earliest records we have of early western Europe. Roman records going back to Julius Caesar seem to indicate that languages and peoples categorized by them as “Celtic” to have been limited to the more central and westerly regions of France.
This view shouldn't be systematized : "Celtic" could mean really different things eventually. Dominique Garcia, for exemple, makes the point of a culture that covered multiple situation (mostly due to what existed before, as in Celto-Ligurians groups).
Giving toponimy and names we had for the period, it seems that Celtic, linguistically speaking, covered more than Comata, but as well Belgia and parts of Germany (German people being themselves largely celtized).
Doesn't mean that you couldn't have large differences, of course, but what we found from continental celtic points out to a more broad presence than just parts of Gaul.
There have also been those who point out that the Romans never specifically give a name to the language of the common people in their British province.
It's a fair point, but that should be really used cautiously. Roman ethnography was based on the idea that they alone (and maybe Greeks) had an history. Everyone else around was supposed fixed in time and socially : Celtic and Germanic people existed the same way they always did (it's not unlike Greek geography, unless more systematized).
With this point of view, it was less interesting to caracterize language than societies (would it be because it's what interested Romans in a process of conquest and/or clientelisation).
That for Romans languages or culture never really changed among non-romanised peoples is to be expected, and I'd be cautious of this bias when using such sources.
The absence of a real linguistical description for Gaul (Aquitani supposedly most different from Celts, when it was a patchwork of more or less importantly celtized people) is a good counter-exemple.
Or the fact that Gallic could be either Celtic Gallic or Gallo-Roman dialects.
he Atrebates and the Belgae for example had branches both on the south coast of Britain and in northern Gaul whilst in south Yorkshire on the banks of the Humber was a tribe called the Parisi said to be related to the tribe that gave its name to the French capital.
It should be taken with a grain of salt. Tendency to identify as same or closely related peoples with a same or similar name isn't the most safe explanation.
It had been wondered, for exemple, if southern Celtic Volcae were related to others tribes named as such : the model of huge migrations of a same people wandering everywhere in Europe may be partially a construction.
It can be said the same for Boii in Bohemia, Italy or Aquitaine : while it's possible to have different branches of a same group originally, these quickly adapted to their new locations and eventually became as distinct culturally as geographically.
(And of course, without talking about Veneti of Gaul, Italy and Baltic, whom same name doesn't mean they were really related).
Now, there's a more important case to be made for Britain and its relations to the continent (for exemple, Eboracum in Parisii region; which could relate to the similar toponim in Gallic Parisii's people). Still, similar toponimy and common origin doesn't means cultural continuum; with Insular Parisii quickly integrating to Briton structures while Continental Parisii passed under Aedui hegemony and eventually went in contact with Rome trough this at the end of Punic Wars.
The archaeological record is said to support this as the more magnificent relics of the pre-Roman past, Stonehenge etc, seem to cluster more to the west than the east where the locals built in the less durable, but more readily available medium of wood.
From what I gathered, the point is far less neholitic (in fact, it's the first time I saw it argued this way) but the more important presence of fortifications and proto-urban structures in Iron Age southern Britain.
It can be easily explained, tough, without using cultural differences (which is really hard to discern trough material culture, while it can be easily argued that a similar material culture doesn't mean a cultural continuity) : the ancient trade between the Mediterranean basin and Southern England (Channel/Seine/Rhone, Channel/Rhine/Danube, or Atlantic) with a more important access to different features than the North.
The presence of possibly related tribes (but I'll nuance it below) could hint to existance of trade relations eventually taken over (not unlike Saxons did eventually).
When the Anglo-Saxon “elite migration” occurred, the new Germanic landlords could well have found that their new tenants spoke a dialect of their own tongue that they could comprehend and very quickly adopt.
While it's most probable (I won't say certain, but I'm thinking it out loud) that you had Germanic settlements in Britian since at least the IIIrd century (the Saxon Shore is a good candidate), it can't be the only one explanation.
For instance, gallic coasts and borders recieved their fair share of Germanic settlement since the Ist century (refugees, migrants, laeti, etc.) and even more since the IIIrd century (with the countepert of Saxon Shore in Gaul as well) without for these groups forming a preparation to germanisation.
It's actually quite the contrary : with the existence of romanized Germans within Gaul, with northern Gallo-Romans being subject to some germanic influence; and Franks (being quite romanized already even before their entry in Romania); all of that prepared to the inclusion of Franks in the post-imperial Romanity.
The difference with Britain, again, seems to be a more superficial romanisation : few colonies, no municipal model worth of mention past the South-East, less develloped structures, less important contact with Rome before the conquest.
Eventually, it means that the traditional paths on which Romanisation progressed on the continent, didn't allow for a deep change.
As for the greater part of Britain using a Germanic dialect, that's more hard to swallow : Celtic toponimy, while being the only real trace of Insular Celtic in the Antiquity, is still widespread enough.
(Now, the case for Northern Britain, and their relationship with people we don't have real clues with as Picts, could be interesting.)
Even in those areas not conquered by the Anglo Saxons Latin died away to become the preserve of churchmen who even then poorly understood it.
Traces of Imperial latin can be still found in Brythonic languages. It's essentially a matter of influence of late Latin and clerical Latin but it exists in a way that didn't in Anglo-Saxon even in Christianized times.
As for Latin being poorly understood in Early medieval England, I must strongly disagree : at the contrary, by the advent of Carolingians, English latinists were considered as the best in Europe.