색연필 (色鉛筆) is actually pronounced 생년필. An intervening ㄴ is inserted to replace the null initial between two morphemes 색 and 연필. This kind of insertion is most likely to happen when the following morpheme begins with a /j/ (이, 여, 야, 요, 유, 예, 얘) and the previous morpheme ends with any 받침, but there is no clear rule and many exceptions as well as variation between speakers.
색연필 used to be spelled as 색년필; however, as the spelling changed the pronunciation remained the same.
Is there a perception of certain consonants as being difficult to palatalize/syllables with onset being difficult to insert /j/ into?
Actual colored pencils are not commonly used in Korea. Don't be shrprised if you get a crayon instead. 색연필 is what we might call a crayon.
They are more akin to a crayon than a color pencil. Don't be surprised when you ask for one.