What should constitute knowledge bases that we expect our future teachers to gain related to pedagogically sound technology integration? Employing the Shulman's teacher knowledge base as a theoretical lens, this study examined the complexity of pre-service teachers' technological pedagogical content knowledge (TPCK) in the context of integrating problem based learning (PBL) and information and communications technology (ICT). Ninety-seven pre-service teachers in this study engaged in a collaborative lesson design project where they applied pedagogical knowledge about PBL to design a technology integrated lesson in their subject area of teaching. Data were collected from two sources: survey and lesson design artifacts. Data analyses revealed that while participants had theoretical understandings of pedagogical knowledge about PBL, their lesson designs showed a mismatch among technology tools, content representations, and pedagogical strategies, indicating conflicts in translating pedagogical content knowledge into designing pedagogically sound, technology integrated lessons. The areas that students perceived to be particularly challenging and difficult include: a) generating authentic and ill-structured problems for a chosen content topic, b) finding and integrating ICT tools and resources relevant for the target students and learning activities, and c) designing tasks with a balance between teacher guidance and student independence. The present study suggests the potential of two explanations for such difficulties: lack of intimate connection among beliefs, knowledge, and actions, and insufficient repertoires for teaching with technology for problem based learning.