Origin: Latin or Celtic
Meaning: Possibly "a hard or rocky land" or "a land of hard men"
Other forms: N/A
This is one place name I can get behind, 100%. The Romans gave the name Caledonia to what is today Scotland, and is used as a poetic name for, like Britannia for Britain. It may be related to the dominant Caledonii tribe, who were Pictish. Another theory is that it comes from caled the Proto-Celtic word for "hard". Others say the word is pre-Celtic.
Sìdh Chailleann is the Scottish Gaelic name for the mountain Schiehallion, and means "fairy hill of the Caledonians". Scotland has many interesting animals that live there, from the ptarmigan and stoat that live high in the mountains, to the seal and golden eagle. The thistle is the floral emblem of Scotland, and the national animal is the unicorn, which has been a Scottish heraldic symbol dating all the way back to the 12th century.
Caledonia has a lovely, romantic sound. I could imagine it being the name of a Princess in a Medieval fairy tale. I also think it is a pretty way of honoring one's Scottish heitage.