Only the northern part of Scotland was called Caledonia by the Romans. The Caledonii (or Caledones) were one of the many Pictish tribes of the area. But apparently powerful enough to have a whole region named after them. Some of the earliest records of this tribe are in Ptolemy's writings. Caledones may mean 'the hard ones'. Somewhere else I've seen it translated as 'stern'.