Advice for Graduate School in Computer Science I am looking for some advice and feedback.

Background: I am an undergraduate mathematics student, with an interest in theoretical computer science (computational complexity, graph theory, combinatorics). I want to pursue a PhD in Computer Science and focus on theory.

My background is in mathematically intensive areas of computer science, but I lack a more applied background in computer science. Specifically I need to complete courses in Programming, Algorithms, Operating Systems, &amp; Databases as prerequisite work for a PhD program. I cannot fit these courses in before graduation. To remedy this I plan to enter the work force and complete a MS part time (so I can pay for the MS), then upon completion of the MS degree enter a full time PhD program.

Question: Would I be at a disadvantage by completing a MS degree part time, prior to entering a PhD program, as opposed to CS students that enter a PhD program immediately upon the completion of their undergraduate degree? The position I work in would be related to CS and would give me transferable skills to a CS program &amp; may help lead me to better focused research. I am just hoping this path does not put me at any kind of disadvantage (in terms of acceptance to a PhD program). I am interested in doing the MS thesis track, and realize that it may take me a little longer to complete the MS degree (since it would be part time). Upon completion of the MS, as stated, I would enter a full time PhD program. 

I am just looking for some feedback and advice. Thanks for your help!
I want to disagree slightly with Dave Clarke and Lev Reyzin.  At least in my department, PhD admission standards for students with MS degrees are higher than for students with only bachelor's degrees.  Additional experience can be a disadvantage, if it isn't enough additional experience.

All else being equal, my department expects any applicant with an MS to have a publication, or at least a publishable result, before we will consider them for admission to the PhD program.  (And by "published", I mean in a reputable peer-reviewed web-accessible conference proceedings or journal, not just a master's thesis, internal technical report, student research conference, or The Inaccessible Chinese Journal of Computer Science.)  Working a full time job is unlikely to leave you enough time—or more importantly, enough mental energy—to do publishable research.

Of course, ceterus is never paribus.  We do soften the de facto publication requirement for  MS applicants who have switched major fields.  But then you're in the uncomfortable position of explaining a perceived weakness.  (On the other hand, I'm not sure switching from mathematics to theoretical computer science counts as "major".)

My advice is not to put your eggs in one basket.  First, talk to people you might work with in the programs you are interested in.  Let me emphasize the plurals here — talk to multiple people in multiple departments.  Second, in the absence of specific contradictory advice from target departments, apply to both MS and PhD programs.  (Some universities, or at least their web forms, stupidly make you pick one or the other, in which case you must talk directly to the admissions office of your target department.)  Sane PhD programs let incoming students from other fields take undergrad CS courses for remediation.