During training at the Complementary Formation Program (CFP), Colombian primary school teachers do not acquire Computational Thinking (CT) skills, which are considered fundamental for the knowledge economies of the 21st century. In this paper, we describe the early stages of a project aiming to reform the CFP curriculum, such that CT skills becomes an integral part. As a first step, we carried-out four introductory workshops with 64 first-and third-semester CFP students and then surveyed them to gather their perceptions on CT. The results show that the students have a limited understanding of CT and its associated skills, but they recognize their importance. Moreover, they agree that primary school should be the starting point to develop them. The project will continue gathering information from current CFP teachers, current primary school teachers, and university professors who are experts in curriculum development, to develop the curricular proposal.