During that time, the traditional scottish clan structure was well on its way to being assimilated into the general European feudal system, with clans becoming fiefs, and clan chiefs becoming titled nobility. However, it is my impression that the clan traditions contributed to a more harmonious relationship between the nobles and the commons in Scotland vs other european nations. (of course, it could have been the poverty, too)
The Highlands were in general more clannish, with stronger ancestral traditions. The Lowlands were a bit more mainstream european, while clans existed there, they were more apt to have a feudal type system imposed upon it.
Don't overlook the influence of powerful foreign settlements and so forth: Norse settled the islands and much of the coasts (highlands), leading to an number of nordic clan names (eg, clan Armstrong) as well as a variety of norse feudal customs. Then there was the strong french influence, brought on by Scotland's traditional alliance with France against England. French nobles and other settlers came and settled in the Scottish lowlands, giving them a more feudal and continental nature. This started under King David in 1140ish.