I published something on this elsewhere in another message section but it is possibly important enough to start its own little section for debate (and at the risk of somewhat repeating myself):

I am using PH Reaney's "A dictionary of British surnames" Routledge & Kegan Paul reprinted 1976. Reaney also refer to GF Black (Black) "The surnames of Scotland" New York, 1946.

Reaney himself states quite clearly that the English Caldwell (versions through to Cholwell) comes from old English ceald weille which case has been elegantly put on this site already.
Reaney also says that "In Scotland Caldwell and Coldwell, formerly pronounced Carwall, are from Caldwell (Renfrewshire). ie: surname taken from placename.

For the sake of debate we might consider if the place was named in Celtic British times after the inhabitants of that area and this name was also a generic name for a lowland tribe or clan.

This is a possible Celtic source for the name:

Gauld: Jas Gald 1550 Black; John Gauld 1686 ib. Gaelic gallda 'pertaining to the lowlands' vesions Gall, Galt

Galt, Gault, ...:
...
In Scotland, like Gall, it is found in Perth & Aberdeen (as Gaut in 1649) and is regarded by Scots as a variant of Gaul or Gauld.

Wallis through to Wallas: ... "Welshman, Celt" ....
Wallace is a Scottish form. Here it means a Briton from the kingdom of Strathclyde where we find Richard Walensis or Waleis between 1165 and 1173. Walace is found in 1432 and Wallas in 1497 (Black).

Wallis unfortunately is probably not Gaelic but the Gaelic name is Uallas which is not dissimilar.

If the name-parts are placed together we get:

Gaulduallas or Gauldwallys
With Scots pronunciation stresing the early syllables the "ys" on the end could easily become plain "s". We only need the "G" to become a "C" to arrive at Cauldwalls - a manner in which I have seen the name spelled.

I have never seen a reference to the name starting with a "G" but the two characters are so similar and the writing style of the old clerks and notaries so hard to decypher that this could easily have been missed.

If this theory is correct the name could simply have been a generic name for the "Lowland Welsh".

Where does this leave the English Caldwell's?
1) they could have come from Scotland through the Scots holding of the Honour of Huntingdon (possible but unikely to account for the wide dispersal of the name in England).
2) the English were named after the various properties of that name in several localities - the English name occurred quite separately and its spelling just became co-incidental. (anyone for DNA testing?)
3) there were Gauldwallys/Caldwells on the Welsh borders who "got" their name for the same reason as it might have been established in Scotland. These Caldwells came to Scotland with the FitzAllans and de Morvilles as is commonly believed.

Its a new idea bu I think it worthy of noting at least.