Could a Masters degree actually make someone a less employable candidate? Let me preface by saying I'm studying Computer Science, so I don't know how well this applies to every field but this is what I have heard from. many Computer Science and Engineering majors.

I have heard that, when applying for jobs, a masters degree can be a sign of poor performance. That is, those with a masters in Computer Science are thought to be significantly poorer programmers than those with an undergraduate. 

I am interested in getting a masters degree because I hope to one day transition into more analytical and research based positions, but if I get an MSc. could it hold me back? Would it be better to get some work experience, and then get my masters mid-career? I know that some employers may even pay for your graduate studies, but is this significantly better than the alternative in any sense?
I would actually think it is precisely the opposite: generally, a computer science Masters requires a thesis, and that thesis usually involves writing a big chunk of functioning code of some sort.  Accomplishing that indicates that person is capable of a accomplishing a large and complex task with minimal supervision.  With an undergraduate degree, you don't necessarily know whether they've ever built a real program that wasn't handed to them as a pre-digested problem as part of their curriculum.

Now, if somebody was a giant company looking for "cannon fodder" programmers to grind out massive repetitive projects, maybe that could be a minus.  Likewise, you have to pay people better when they've got a Masters, commensurate with their increase in skill, so if somebody is looking for low-quality coding work, a Masters could make a candidate overqualified.  However, if you're thinking about eventually moving toward more research in your career, do you really want those sort of jobs?

I know for a fact, however, that the company group I'm in rarely even considers hiring people without at least a Masters.  A number of others I know are similar: the more cutting-edge or research-oriented a company is, the more that they are likely to value that extra education.