Transitioning from pure research to a teaching position I have a PhD in Computer Science and have been working as a "pure researcher" in an academic setting for the past 10+ years. I have a decent publication record, with a large number of citations to my work. As part of the research role, I have also been a co-supervisor/advisor of several PhD students and done presentations in front of conference audiences. I've done a bunch of "guest lectures" in a few undergraduate classes.

I'd like to transition from the current pure research position to a mixed teaching and research role. My motivations are to have more contact with people (as research can be lonely) and better job security. To than end I've applied for several teaching positions (tenure-track associate professor), but I've been told that the lack of teaching/lecturing experience (undergraduate students) is a problem.

Why would the selection committee see the lack of teaching experience as a deal-breaker?

I do understand that teaching requires a different set of skills than research. However, teaching skills can be learned, so is this a case of demonstrating the capability of learning such skills?  If so, what would be some acceptable strategies for obtaining such skills?
It's true that teaching skills can be learned.  But some people underestimate the amount of work required to do so, or do not commit to putting it in, or remain tied to ineffective philosophies of teaching, and thus do not become good teachers.  Others do, but it takes them some time, and in the meantime they don't do as well.

All other things equal, a search committee would rather hire someone who has already been through this, and will be able to walk in and teach well from day one, rather than needing a potentially long period to adjust (during which they will have to explain to their dean why this new hire's teaching evaluations are so poor).  Especially since you are applying at a more senior level (associate professor), your competitors likely have 5 years or more of teaching experience, and evaluations, letters, etc, that show that they are effective teachers.  Lacking that, it's understandable that you would be at a significant disadvantage.

It seems to me that the most natural course of action would be to see if you can pick up some teaching at your current institution.  Approach your chair and express your interest in teaching a class or two if the opportunity arises.  There will likely come a time when the chair just can't get all the classes covered, and would ordinarily consider looking for an adjunct, visitor, or graduate student to teach a class - then she will think of you.  If you pull it off with reasonable success, and make it known that you are receptive to continuing to teach, you will likely get more opportunities.  Eventually you can build up sufficient experience to be a good candidate for a different job - or maybe you'll find that your existing job, plus occasional teaching, satisfies you after all.  (Or maybe you'll find that you don't in fact enjoy teaching, and stick to the job you have.)

I'd think that this sort of gradual phase-in of teaching duties is likely to go better and be less stressful on the whole.  Even if you were able to get a full-time teaching job, you'd likely be asked to start teaching 2-3 courses per semester right off the bat - with no prior experience, that can be a pretty severe shock.